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 |
哪位能帮忙看一下,哪有逻辑错误,,,WA 不知为什么,#include<iostream> #include<queue> #include<string.h> #include<bitset> #include<memory> #include<cstdio> using namespace std; typedef bitset <16> piece; int cnt; struct Stat { piece value; int index; Stat (piece x,int y):value(x),index(y){}; Stat (){}; } ; Stat stat,temp; struct situation { int step; int pre; int x; int y; }; struct point { int x; int y; }; queue<Stat> q; point index [70000]; situation store[70000]; bool visit[70000]; piece offset[16]={0xf888,0xf444,0xf222,0xf111, 0x8f88,0x4f44,0x2f22,0x1f11, 0x88f8,0x44f4,0x22f2,0x11f1, 0x888f,0x444f,0x222f,0x111f,}; void bfs(Stat start) { visit[start.value.to_ulong()]=true; memset(visit,false,sizeof(visit));//一定要在BFS 里面 q.push (start); while(!q.empty()) { stat=q.front(); q.pop(); if (stat.value.to_ulong()==0) { cout<<store[stat.index].step<<endl; int counter=0; for(int i=stat.index;store[i].pre!=-1;i=store[i].pre) { index[counter].x=store[i].x; index[counter].y=store[i].y; counter++; } for(int i=counter-1;i>=0;i--) cout<<index[i].x<<" "<<index[i].y<<endl; return ; } for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) { temp.value=stat.value^offset[(i-1)*4+j-1]; if(!visit[temp.value.to_ulong()]) { visit[temp.value.to_ulong()]=true; q.push(temp); temp.index=cnt; store[cnt].x=i; store[cnt].y=j; store[cnt].pre=stat.index; store[cnt].step=store[stat.index].step+1; cnt++; } } } } int main() { freopen("in.txt","r",stdin); freopen ("out.txt","w",stdout ); string g=""; char ch; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { ch=getchar(); if(ch=='-') g+="0"; else g+="1"; } getchar(); } piece p(g); store[0].pre=-1; store[0].step=0; cnt=1; bfs(Stat(p,0)); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator