BFS. bfs的时候应是一整行一整列的扩展,而不是只扩展周围四个点.见代码:
#include<iostream>
#include<queue>
using namespace std;
int dir[4][2]=
{0,-1,0,1,-1,0,1,0};
char board[80][80];
bool vis[80][80];
int w,h;
typedef struct
{
int x,y;
int num,cur;
}node;
int dir_lookup(int x,int y)
{
if(x==0&&y==-1) return 0;
if(x==0&&y==1) return 2;
if(x==1&&y==0) return 1;
if(x==-1,y==0) return 3;
}
int bfs(int begx,int begy,int endx,int endy)
{
node temp;
queue<node> ss;
vis[begy][begx]=true;
temp.x=begx;
temp.y=begy;
temp.cur=-1;
temp.num=0;
ss.push(temp);
while(!ss.empty())
{
temp=ss.front();
ss.pop();
node tp;
for(int i=0;i<4;i++)
{
tp.x=temp.x+dir[i][0];
tp.y=temp.y+dir[i][1];
tp.cur=dir_lookup(dir[i][0],dir[i][1]);
if(tp.cur!=temp.cur||temp.cur==-1)
tp.num=temp.num+1;
else tp.num=temp.num;
while(1)
{
if(tp.x>=0&&tp.x<=w+1&&tp.y>=0&&tp.y<=h+1&&!vis[tp.y][tp.x])
{
if(tp.x==endx&&tp.y==endy||board[tp.y][tp.x]==' ')
{
vis[tp.y][tp.x]=true;
if(tp.x==endx&&tp.y==endy)
return tp.num;
ss.push(tp);
tp.x=tp.x+dir[i][0];
tp.y=tp.y+dir[i][1];
}
else break;
}
else break;
}
}
}
return -1;
}
int main()
{
int test=1;
while(scanf("%d%d",&w,&h)!=EOF&&(w||h))
{
int i,j;
for(i=1;i<=h;i++)
{
getchar();
for(j=1;j<=w;j++)
scanf("%c",&board[i][j]);
}
for(i=0;i<=w+1;i++)
{
board[0][i]=' ';
board[h+1][i]=' ';
}
for(i=0;i<=h+1;i++)
{
board[i][0]=' ';
board[i][w+1]=' ';
}
printf("Board #%d:\n",test++);
int x1,y1,x2,y2;
int p=1;
while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF&&(x1+y1+x2+y2))
{
printf("Pair %d: ",p++);
memset(vis,0,sizeof(vis));
int cnt=bfs(x1,y1,x2,y2);
if(cnt!=-1) printf("%d segments.\n",cnt);
else printf("impossible.\n");
}
printf("\n");
}
//system("pause");
return 0;
}
posted on 2010-08-13 17:23
wuxu 阅读(199)
评论(0) 编辑 收藏 引用 所属分类:
搜索