NC15434 wyh的迷宫
2022/7/15 23:23:33
本文主要是介绍NC15434 wyh的迷宫,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
题目
题目描述
给你一个n*m的迷宫,这个迷宫中有以下几个标识:
s代表起点
t代表终点
x代表障碍物
.代表空地
现在你们涵哥想知道能不能从起点走到终点不碰到障碍物(只能上下左右进行移动,并且不能移动到已经移动过的点)。
输入描述
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据,对于每一组测试数据,第一行输入2个数n和m(1<=n,m<=500)
接下来n行,每行m个字符代表这个迷宫,每个字符都是上面4个中的一种
数据保证只有一个起点和一个终点
输出描述
对于每一组测试数据,如果可以的话输出YES,不可以的话输出NO
示例1
输入
1 3 5 s...x x...x ...tx
输出
YES
题解
知识点:DFS,BFS。
这道题两种搜索都能写,但dfs会好一点,因为bfs是所有路径都推到最后一步才出结果,不适合可行性的题,但如果地图太大的话,还是用bfs。
时间复杂度 \(O(?)\)
空间复杂度 \(O(mn)\)
代码
#include <bits/stdc++.h> #define ll long long using namespace std; int n, m; char dt[507][507]; bool vis[507][507]; const int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; bool dfs(int x, int y) { if (dt[x][y] == 't') return true; for (int i = 0;i < 4;i++) { int xx = x + dir[i][0]; int yy = y + dir[i][1]; if (xx < 0 || xx >= n || yy < 0 || yy >= m || vis[xx][yy] || dt[xx][yy] == 'x') continue; vis[xx][yy] = 1; if (dfs(xx, yy)) return true; } return false; } bool solve() { memset(vis, 0, sizeof(vis)); cin >> n >> m; int sx, sy; for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { cin >> dt[i][j]; if (dt[i][j] == 's') sx = i, sy = j; } } vis[sx][sy] = 1; if (dfs(sx, sy))return true; return false; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << '\n'; else cout << "YES" << '\n'; } return 0; }
这篇关于NC15434 wyh的迷宫的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!