BFS板子题
2024-10-20 05:20:44
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
bool in(int x, int y)
{
return 0 <= x && x < n && 0 <= y && y < m;
}
struct node
{
int x,y,d;
node (int xx, int yy,int dd)
{
x = xx;
y = yy;
d = dd;
}
};
int bfs(int sx, int sy)
{
queue<node> q;
q.push(node(sx,sy,0));
vis[sx][sy] = true;
while (!q.empty())
{
node now = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int tx = now.x + dir[i][0];
int ty = now.y + dir[i][1];
if (in(tx,ty) && maze[tx][ty] != '*' && !vis[tx][ty])
{
if (maze[tx][ty] == 'T')
{
return now.d + 1;
}
else
{
vis [tx][ty] = true;
q.push(node(tx,ty,now.d + 1));
}
}
}
}
return -1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> maze[i];
}
int x, y;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (maze[i][j] == 'S')
{
x = i, y = j;
}
}
}
cout << bfs(x,y) << endl;
return 0;
}
最新文章
- JS正则表达式元字符
- AOP学习心得&;jdk动态代理与cglib比较
- Geometry Curve of OpenCascade BRep
- 使Eclipse符合Java编程规范
- Web Api 2 接口API文档美化
- 转载一篇文章 python程序员经常犯的10个错误
- Android 用户界面---拖放(Drag and Drop)(二)
- Java的导入与导出Excel
- 浅析PAC,教你动手修改你的PAC文件及user-rule文件实现自动代理
- jquery正则表达式显示文本框输入范围 只能输入数字、小数、汉字、英文字母的方法
- spring之注解详解
- 最优化方法:范数和规则化regularization
- .NET Core TDD 前传: 编写易于测试的代码 -- 依赖项
- 转 - Linux安装python3.6
- 20172310 实验四 Android程序设计
- Visual Question Answering with Memory-Augmented Networks
- Shell Trap信号管理
- bug定位
- python threading模块2
- 软件工程作业 - Week 1