POJ - 3984 迷宫问题 bfs解法

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
int a[][],b[][];
int di[][]={,,,-,,,-,};
void bfs(int x,int y)
{
int tx=x,ty=y,i;
if(a[x][y]==)
{
a[x][y]=;
for(i=;i<;i++)
{
tx+=di[i][];
ty+=di[i][];
if(a[tx][ty]==&&tx>=&&ty>=&&tx<=&&ty<=)
{
b[tx][ty]=min(b[tx][ty],b[x][y]+);
}
}
for(i=;i<;i++)
{
tx+=di[i][];
ty+=di[i][];
if(a[tx][ty]==&&tx>=&&ty>=&&tx<=&&ty<=)
bfs(tx,ty);
}
}
}
int main()
{
stack<int>s1,s2;
int i,j,ti,tj,k;
for(i=;i<;i++)
for(j=;j<;j++)
scanf("%d",&a[i][j]);
for(i=;i<;i++)
for(j=;j<;j++)
b[i][j]=;
b[][]=;
bfs(,);
i=;j=;
s1.push();
s2.push();
while()
{
if(j==&&i==)
break;
for(k=;k<;k++)
{
ti=i+di[k][];
tj=j+di[k][];
if(b[i][j]==b[ti][tj]+ && ti>= && tj>= && ti<= && tj<=)
{
s1.push(ti);
s2.push(tj);
i=ti;j=tj;
// printf("%d %d\n",i,j);
break;
}
}
}
while(s1.size()!=)
{
i=s1.top();s1.pop();
j=s2.top();s2.pop();
printf("(%d, %d)\n",i,j);
}
return ;
}
上一篇:github不小心同步覆盖了本地文件


下一篇:Git命令行连Github与TortoiseGit 连Github区别