1368.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
int set[3][3][3][3];
int map[7][7][4];
int n,m;

int div(char c)
{switch(c)
{case 'O':return 0;
 case 'F':return 1;
 case 'I':return 2;
 default:return -1;
}
}


void init()
{int i,j,a[4];char c;
memset(set,0,81*sizeof(int));

for(i=0;i<n*m;i++)
{for(j=0;j<4;j++)
 {cin>>c;a[j]=div(c);}
  set[a[0]][a[1]][a[2]][a[3]]++;
}
for(i=0;i<=n;i++)map[i][0][1]=1;
for(i=0;i<=m;i++)map[0][i][2]=1;
}


int find(int a,int b)
{int u,l,d,r;
u=2-map[a-1][b][2];
l=2-map[a][b-1][1];

if(a==n){if(b==m)return set[u][1][1][l]==1;
	d=1;
	for(r=0;r<3;r+=2)
	if(set[u][r][d][l]){
		set[u][r][d][l]--;
	        map[a][b][1]=r;
	       if(find(a,b+1))return 1;
	        set[u][r][d][l]++;
				}
	return 0;
	}
else {if(b==m){for(d=0;d<3;d+=2)
	       if(set[u][1][d][l]){
		       set[u][1][d][l]--;
	      		 map[a][b][2]=d;
	       		if(find(a+1,1))return 1;
	       	       set[u][1][d][l]++;
	                            }
		return 0;
		}
	for(r=0;r<3;r+=2)
	for(d=0;d<3;d+=2)
	if(set[u][r][d][l]){
		set[u][r][d][l]--;
	        map[a][b][1]=r;
		map[a][b][2]=d;
		if(find(a,b+1))return 1;
		set[u][r][d][l]++;
				}
	return 0;
	}
}					                                              
int main()
{while(1)
	{cin>>n>>m;
	if(n==0&&m==0)break;
        init();
	if(find(1,1))cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	}
return 0;
}