记录编号	97109	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO Dec08] 跳棋获胜	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.064 s
提交时间	2014-04-16 22:00:53	内存使用	4.93 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<deque>
#include<queue>
using namespace std;
const int SIZEn=510,SIZEN=500*500/2+10;
int n;
char board[SIZEn][SIZEn]={0};
int mod4[SIZEn][SIZEn]={0};
int id[SIZEn][SIZEn]={0};//每个格所对编号
int idx[SIZEN]={0},idy[SIZEN]={0};
int N=0,checknum=0;
class EDGE{
public:
	int from,to;
	bool w;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
deque<int> path;
int sing[2]={0};
void DFS(int x){
	for(int i=0;i<c[x].size();i++){
		EDGE &e=edges[c[x][i]];
		if(!e.w){
			e.w=true;
			edges[c[x][i]^1].w=true;
			DFS(e.to);
		}
	}
	path.push_front(x);
}
void printans(void){
	for(int i=0;i<path.size();i++){
		printf("%d %d\n",idx[path[i]],idy[path[i]]);
	}
}
void label_clear(void){//所有的边置为未访问
	for(int i=0;i<edges.size();i++) edges[i].w=0;
}
void work(void){
	bool flag[4]={0};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(board[i][j]=='K'){
				if(!c[id[i][j]].size()) continue;
				if(flag[mod4[i][j]]) continue;
				int k=sing[mod4[i][j]/2];
				if(k!=0&&k!=2) continue;
				if(k==2&&!(c[id[i][j]].size()&1)) continue;
				flag[mod4[i][j]]=true;
				label_clear();
				path.clear();
				DFS(id[i][j]);
				if((k==2&&path.size()==checknum+1)||(k==0&&path.size()==checknum)){
					printans();
					return;
				}
			}
		}
	}
	printf("impossible\n");
}
void addedge(int a,int b){
	edges.push_back((EDGE){a,b,0});
	edges.push_back((EDGE){b,a,0});
	int tot=edges.size()-2;
	c[a].push_back(tot);
	c[b].push_back(tot+1);
}
void init(void){
	scanf("%d\n",&n);
	char str[SIZEn]={0};
	for(int i=1;i<=n;i++){
		scanf("%s",str);
		for(int j=1;j<=n;j++){
			board[i][j]=str[j-1];
			mod4[i][j]=(i+j)%4;
			if(board[i][j]!='-'){
				N++;
				idx[N]=i,idy[N]=j;
				id[i][j]=N;
			}
		}
		scanf("\n");
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(board[i][j]=='o'){//建立一条边
				checknum++;
				if(i>1&&i<n&&j>1&&j<n){
					addedge(id[i-1][j+1],id[i+1][j-1]);
					addedge(id[i-1][j-1],id[i+1][j+1]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(c[id[i][j]].size()&1) sing[mod4[i][j]/2]++;
		}
	}
}
int main(){
	freopen("winchk.in","r",stdin);
	freopen("winchk.out","w",stdout);
	init();
	work();
	return 0;
}