Poj Solution 1368

http://poj.org/problem?id=1368

#include<iostream>
#include"memory.h"
using namespace std;
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;
}    
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *