二手交易网站建设的功能定位,网站设计制作公司排名,360报危险网站,9uu最新域址永久1.题目描述 机器猫被困在一个矩形迷宫里。 迷宫可以视为一个n x m 矩阵#xff0c;每个位置要么是空地#xff0c;要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。 机器猫初始时位于(1,1)的位置#xff0c;问能否走到(n,m)位置。
2.输入格式 第一行#xff0…1.题目描述 机器猫被困在一个矩形迷宫里。 迷宫可以视为一个n x m 矩阵每个位置要么是空地要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。 机器猫初始时位于(1,1)的位置问能否走到(n,m)位置。
2.输入格式 第一行两个正整数 n,m。 接下来几行输入这个迷宫。每行输入一个长为 m 的字符串#表示墙. 表示空地。 3.输出格式 仅一行一个字符串。如果机器猫能走到(n,m)则输出 Yes;否则输出 No 。 4.输入输出样例 1.输入
3 5
.##.#
.#...
...#.
2.输出
Yes
5.说明/提示 样例解释 路线如下:(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)
数据规模与约定 对于 100% 的数据保证1 n,m 100(1,1)和(n,m)均为空地。 代码
#include stdio.h
#include stdlib.h#define MAXN 1000typedef struct {int x, y;
} Point;int n, m;
char maze[MAXN][MAXN 1];
int visited[MAXN][MAXN]; // 访问标记
Point queue[MAXN * MAXN]; // 队列用于 BFS
int front 0, rear 0;// 移动方向上下左右
int dir[4][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};void enqueue(Point p) {queue[rear] p;
}Point dequeue() {return queue[front];
}int is_valid(int x, int y) {return (x 0 x n y 0 y m maze[x][y] . !visited[x][y]);
}int bfs() {enqueue((Point){0, 0}); // 从 (0,0) 开始visited[0][0] 1; // 标记为已访问while (front rear) {Point current dequeue();// 如果到达终点 (n-1, m-1)if (current.x n - 1 current.y m - 1) {return 1; // 可到达}// 检查四个方向for (int i 0; i 4; i) {int new_x current.x dir[i][0];int new_y current.y dir[i][1];if (is_valid(new_x, new_y)) {visited[new_x][new_y] 1; // 标记为已访问enqueue((Point){new_x, new_y}); // 入队}}}return 0; // 不可到达
}int main() {scanf(%d %d, n, m);// 读取迷宫for (int i 0; i n; i) {scanf(%s, maze[i]);}// 如果起点或终点是墙直接输出 Noif (maze[0][0] # || maze[n-1][m-1] #) {printf(No\n);return 0;}// 执行 BFSif (bfs()) {printf(Yes\n);} else {printf(No\n);}return 0;
}
