解题思路:
注意事项:
参考代码:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
int x, y;
}t;
queue <node> q;
int dx[] = {0, 0, -1, 1}; //位移方向
int dy[] = {-1, 1, 0, 0};
int main()
{
bool a[105][105]; //0为未走过,1为走过或者障碍
int T;
cin>>T;
while(T--)
{
int m, n;
cin>>m>>n; //行 列
memset(a, 0, sizeof(a));
int x0, y0, x1, y1;
char temp;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> temp;
if (temp == 'S') x0 = i, y0 = j;
if (temp == 'E') x1 = i, y1 = j;
if (temp == '#') a[i][j] = 1;
}
}
//开始广度优先遍历咯
int s = 0; //计算步数
a[x0][y0] = 1;
q.push(node({x0, y0})); //起点入队
bool flag = 1; //用以区分是队空还是找到终点,退出循环的
while (!q.empty() && flag) //寻找是队空还是找到终点
{
s++;
int size = q.size();
for (int i = 1; i <= size; i++)
{
t = q.front(); //取队头
q.pop(); //删队头
for (int j = 0; j < 4; j++)
{
int x = t.x + dx[j];
int y = t.y + dy[j];
if (x >= 1 && x <= m && y >= 1 && y <= n && a[x][y] == 0)
{
a[x][y] = 1;
if (x == x1 && y == y1) flag = 0; //到终点了
else q.push(node({x, y})); //新点入队
}
}
}
}
if (!flag) cout<<s<<endl;
else cout<<-1<<endl;
}
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:533 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:563 |
母牛的故事 (C语言代码)浏览:1301 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:598 |
C语言程序设计教程(第三版)课后习题9.4 (Java代码)浏览:1421 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:768 |
简单的a+b (C语言代码)浏览:825 |
The 3n + 1 problem (C语言代码)浏览:554 |
IP判断 (C语言描述,蓝桥杯)浏览:1096 |
字符逆序 (C语言代码)浏览:622 |