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