记录编号	97093	评测结果	AAAAWAAWAWWWWWW
题目名称	1597.[USACO Dec08] 跳棋获胜	最终得分	46
用户昵称	cstdio	是否通过	未通过
代码语言	C++	运行时间	0.047 s
提交时间	2014-04-16 21:27:59	内存使用	1.11 MiB

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include<cstring>
using namespace std;

#define E (-1)
#define U (0)
#define O (1)
#define K (2)
//empty, unoccupied, opponent, king

char c;
int opp=0,vp;
int N;

int arr[205][205];
int vi[70000];
int vj[70000];

bool used[205][205];
int epos[205][205];

int dr[4] = {2,2,-2,-2};
int dc[4] = {2,-2,2,-2};

void rec(int i,int j){
	while(epos[i][j]<4){ //while we still have unused edges at this vertex
		if(i+dr[epos[i][j]]<0) epos[i][j]++;        //if this edge takes us out of bounds, skip it
		else if(i+dr[epos[i][j]]>=N) epos[i][j]++;  
		else if(j+dc[epos[i][j]]<0) epos[i][j]++;
		else if(j+dc[epos[i][j]]>=N) epos[i][j]++;
		else if(arr[i+dr[epos[i][j]]/2][j+dc[epos[i][j]]/2]!=O) epos[i][j]++; //if the square underneath this edge isn't an opposing piece, skip it
		else if(arr[i+dr[epos[i][j]]][j+dc[epos[i][j]]]!=U) epos[i][j]++; //if the square on the other side of this edge is occupied, skip it
		else if(epos[i+dr[epos[i][j]]][j+dc[epos[i][j]]]>3-epos[i][j]) epos[i][j]++;
//if we have already traversed this edge in the other direction, skip it
		else {
			epos[i][j]++; //delete this edge and then recurse on it
			rec(i+dr[epos[i][j]-1],j+dc[epos[i][j]-1]);
		}
	}
	vi[vp]=i; vj[vp]=j; vp++; //add this vertex to the path
}

bool sanitize(){
	for(int s=0;s<vp-1;s++){
		if(abs(vi[s+1]-vi[s])!=2) return 0; //check to see that the two adjacent vertices in the path are connected by an edge
		if(abs(vj[s+1]-vj[s])!=2) return 0;
		if(arr[(vi[s+1]+vi[s])/2][(vj[s+1]+vj[s])/2]!=O) return 0; //check to see that the square underneath the edge has an opposing piece
	}
	return 1;
}

int euler(int si,int sj){
	for(int i=0;i<N;i++){
		memset(used[i],0,sizeof(used[i]));
		memset(epos[i],0,sizeof(epos[i]));
	}
	vp = 0;
	arr[si][sj]=U; //set the starting square to be unoccupied
	rec(si,sj); //run Eulerian path algorithm
	arr[si][sj]=K; //put the king back down in the starting square
	if(!sanitize()) return -1; //if the path is invalid, return -1
	return vp; //otherwise, return the number of edges in the path
}

int main(){
	FILE *fin = fopen("winchk.in","r");
	FILE *fout = fopen("winchk.out","w");
	fscanf(fin,"%d",&N);
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			do fscanf(fin,"%c",&c); while(c==' '||c=='\n');
			if(c=='-') arr[i][j]=E;
			if(c=='+') arr[i][j]=U;
			if(c=='o') { arr[i][j]=O; opp++; }
			if(c=='K') arr[i][j]=K;
		}

	int cnte = 0, cnto = 0;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			for(int k=0;k<4;k++)
		
if(arr[i][j]==K&&i+dr[k]/2>=0&&i+dr[k]/2<N&&j+dc[k]/2>=0&&j+dc[k]/2<N&&arr[i+dr[k]/2][j+dc[k]/2]==O){
//check how many kings of each parity touch an edge
				if((i+j)%4==1) cnto++;
				else cnte++;
				break;
			}
	
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			if(cnto!=1&&(i+j)%4==1) continue; //if more than one king of this parity touches an edge, we can't find a solution for this parity
			if(cnte!=1&&(i+j)%4==3) continue;
			if(arr[i][j]==K&&euler(i,j)==opp+1){ //check for a path from each king
				for(int k=vp-1;k>=0;k--) //print the path if it exists
					fprintf(fout,"%d %d\n",vi[k]+1,vj[k]+1);
				fclose(fin); fclose(fout); return 0;
			}
		}
	fprintf(fout,"impossible\n");
	fclose(fin); fclose(fout);
	return 0;
}