[usaco] Chapter2-Bigger Challenges(Section 2.4)

 

/*
ID: bbezxcy1
PROG: ttwo
LANG: C++
*/
#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdio>
using namespace std;
char map[20][20];
bool vis[15][15][15][15][5][5];
int fx,fy,cx,cy,df,dc;
ifstream fin("ttwo.in");
ofstream fout("ttwo.out");

bool check(int y,int x){
	if(y>10||y<1||x>10||x<1||map[y][x]=='*'){
		return 0;
	}
	return 1;
}

int diy[4]={-1,0,1,0};
int dix[4]={0,1,0,-1};
void change(int &x,int &y,int &d){
	int xx,yy,dd;
	for(int i=0;i<4;i++)
	{
	    if(d==i)
	    {
	        xx=x+dix[i];
	        yy=y+diy[i];
            if(check(yy,xx)){
                y=yy;
                x=xx;
            }
            else{
                d=(d+1)%4;
            }
	        break;
	    }
	}
}
int main(){
	int i,j,ans,b,c;
	for(i=1;i<=10;i++){
		fin>>map[i]+1;
		for(j=1;j<=10;j++){
			if(map[i][j]=='F'){
				fy=i;
				fx=j;
			}
			if(map[i][j]=='C'){
				cy=i;
				cx=j;
			}
		}
	}
	//fout<<fx<<" "<<fy<<" "<<cx<<" "<<cy<<endl;
	memset(vis,0,sizeof(vis));
	df=dc=0;
	ans=0;
	while(1)
	{
		if(vis[fx][fy][cx][cy][df][dc]){
			fout<<0<<endl;
			break;
		}
		vis[fx][fy][cx][cy][df][dc]=1;
		if(fx==cx&&fy==cy){
			fout<<ans<<endl;
			break;
		}
		change(fx,fy,df);
		change(cx,cy,dc);
      //  fout<<fx<<" "<<fy<<" "<<cx<<" "<<cy<<endl;
		ans++;
	}
	return 0;
}