| ||||||||||
| 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的思路怎么不行啊????代码!!请大牛们指点下哈!!!#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct IN
{
char ans[4][4];
int x,y;
}temp,num;
//char map[4][4];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
char D[4] = {'u','d','l','r'};
char compare[4][4] = {'1','2','3','4','5','6','7','8','9'};
string result;
int flag;
int visit[4][4];
string bfs()
{
//flag = 0;
result = "";
queue<IN> Q;
int i,j,k;
Q.push(temp);
while(!Q.empty())
{
temp = Q.front();
num = Q.front();
Q.pop();
for(i=0; i<4; i++)
{
flag = 1;
num.x = temp.x + dir[i][0];
num.y = temp.y + dir[i][1];
swap(num.ans[num.x][num.y],temp.ans[temp.x][temp.y]);
result += D[i];
for(j=0; j<3; j++)
{
for(k=0; k<3; k++)
{
if(num.ans[j][k] != compare[j][k])
{
flag = 0;
break;
}
}
if(flag==0) break;
}
visit[num.x][num.y] = 1;
if(flag==1)
return result;
if(num.x>=0 && num.x<3 && num.y>=0 && num.y<3 && !visit[num.x][num.y])
{
Q.push(num);
}
}
}
return "s";
}
int main()
{
int i,j;
char s;
string str;
for(i=0; i<3; i++)
{
for(j=0; j<3; j++)
{
cin>>s;
if(s == 'X')
{
temp.ans[i][j] = '9';
temp.x = i;
temp.y = j;
}
else
temp.ans[i][j] = s;
}
}
memset(visit,0,sizeof(visit));
str = bfs();
if(str == "s")
cout<<"unsolvable"<<endl;
else
cout<<str<<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