|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
int a[11][11] =
|
|
|
{
|
|
|
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
|
|
|
{1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
|
|
|
{1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
|
|
|
{1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
|
|
|
{1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
|
|
|
{1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
|
|
|
{1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
|
|
|
{1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
|
|
|
{1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
|
|
|
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
|
|
|
};
|
|
|
int dir[4][2] = {{-1, 0},
|
|
|
{0, 1},
|
|
|
{1, 0},
|
|
|
{0, -1}};
|
|
|
int vis[11][11];//用来标记有没有走过（有没有在队列中)
|
|
|
int b[11][11];//用来记录bfs的过程
|
|
|
struct Node {
|
|
|
int x, y;
|
|
|
};
|
|
|
queue<Node> q;
|
|
|
|
|
|
int main() {
|
|
|
memset(b, 0, sizeof(b));
|
|
|
memset(vis, 0, sizeof(vis));
|
|
|
while (!q.empty()) q.pop();//初始化队列
|
|
|
|
|
|
Node start;
|
|
|
start.x = 1;
|
|
|
start.y = 1;
|
|
|
vis[1][1] = 1;
|
|
|
b[1][1] = 1;
|
|
|
q.push(start);//把起点放进队列
|
|
|
bool f = 0;
|
|
|
while (!q.empty()) {
|
|
|
Node temp;
|
|
|
temp = q.front();//取出队头元素
|
|
|
q.pop();
|
|
|
int x = temp.x;
|
|
|
int y = temp.y;
|
|
|
if (x == 8 && y == 8)//若走到了
|
|
|
{
|
|
|
f = 1;
|
|
|
Node road[111];//用来记录路径
|
|
|
//for(int i=1;i<=8;i++)//可以通过输出b数组来观察bfs的实现过程
|
|
|
//{
|
|
|
// for(int j=1;j<=8;j++)
|
|
|
// {
|
|
|
// printf("%5d",b[i][j]);
|
|
|
// }
|
|
|
// cout<<endl;
|
|
|
//}
|
|
|
//cout<<b[8][8]<<endl;
|
|
|
int k = 1;
|
|
|
while (!(x == 1 && y == 1))//通过b数组来找到之前是哪一个点走到x，y的
|
|
|
{
|
|
|
road[k].x = x;
|
|
|
road[k++].y = y;
|
|
|
for (int i = 0; i < 4; i++) {
|
|
|
int xx = x + dir[i][0];
|
|
|
int yy = y + dir[i][1];
|
|
|
if (xx < 1 || yy < 1 || xx > 8 || yy > 8) continue;//超出范围的不要
|
|
|
if (b[xx][yy] == b[x][y] - 1) {
|
|
|
x = xx;//倒退回去
|
|
|
y = yy;
|
|
|
break;//一定要跳出，要把更新的x，y放到road里
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
road[k].x = 1;//别忘了把起点放进去
|
|
|
road[k].y = 1;
|
|
|
for (int i = k; i >= 1; i--)//输出路径
|
|
|
{
|
|
|
cout << road[i].x << " " << road[i].y << endl;
|
|
|
}
|
|
|
}
|
|
|
if (f == 1) //找到路了就不用再跑大循环了
|
|
|
break;
|
|
|
|
|
|
for (int i = 0; i < 4; i++)//遍历四个方向
|
|
|
{
|
|
|
int xx = x + dir[i][0];
|
|
|
int yy = y + dir[i][1];
|
|
|
if (a[xx][yy] == 0 && vis[xx][yy] == 0) {
|
|
|
vis[xx][yy] = 1;
|
|
|
Node New;
|
|
|
New.x = xx;
|
|
|
New.y = yy;
|
|
|
b[xx][yy] = b[x][y] + 1;//用来标记走到（xx，yy）是第几步
|
|
|
q.push(New);//放进队列
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
} |
