| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
简单的BFS,就是状态压缩一下就行了【43ms】#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
int op[5][5];
bool vis[70000];
queue<int> xx;
int dx[4]={1,-1,0,0},
dy[4]={0,0,1,-1};
bool ok(int x,int y)
{
if(x>=0&&x<4&&y>=0&&y<4)
return 1;
return 0;
}
int bfs(int st)
{
while(!xx.empty())xx.pop();
int step=0,cur,i,j,k;
xx.push(st);
while(!xx.empty())
{
int t=xx.size();
while(t--)
{
cur=xx.front();
xx.pop();
vis[cur]=1;
if(cur==0||cur==65535)
return step;
else
{
int next;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
next=cur^op[i][j];
for(k=0;k<4;k++)
{
int tx,ty;
tx=i+dx[k];
ty=j+dy[k];
if(ok(tx,ty))
next=next^op[tx][ty];
}
if(!vis[next])
{
xx.push(next);
vis[next]=1;
}
}
}
}
}
step++;
}
return -1;
}
int input()
{
memset(op,0,sizeof(op));
memset(vis,0,sizeof(vis));
int ans=0,cc=0;
char grid[5][5];
int i,j;
for(i=0;i<4;i++)
scanf("%s",grid[i]);
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
op[i][j]=pow(2,cc);
if(grid[i][j]=='w')
ans+=pow(2,cc);
cc++;
}
return ans;
}
int main()
{
int start,i,j;
start=input();
int ans=bfs(start);
if(ans==-1)
cout<<"Impossible"<<endl;
else
cout<<ans<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator