| ||||||||||
| 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