1.題目描述

機(jī)器貓被困在一個(gè)矩形迷宮里。
迷宮可以視為一個(gè)n x m 矩陣，每個(gè)位置要么是空地，要么是墻。機(jī)器貓只能從一個(gè)空地走到其上、下、左、右的空地。
機(jī)器貓初始時(shí)位于(1,1)的位置，問(wèn)能否走到(n,m)位置。

2.輸入格式

第一行，兩個(gè)正整數(shù) n,m。
接下來(lái)幾行，輸入這個(gè)迷宮。每行輸入一個(gè)長(zhǎng)為 m 的字符串，#表示墻，. 表示空地。

3.輸出格式

僅一行，一個(gè)字符串。如果機(jī)器貓能走到(n,m)，則輸出 Yes;否則輸出 No 。

4.輸入輸出樣例

1.輸入：

3 5
.##.#
.#...
...#.

2.輸出：

Yes

5.說(shuō)明/提示

樣例解釋
路線如下:(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)

數(shù)據(jù)規(guī)模與約定
對(duì)于 100% 的數(shù)據(jù)，保證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]; // 訪問(wèn)標(biāo)記
Point queue[MAXN * MAXN]; // 隊(duì)列用于 BFS
int front = 0, rear = 0;// 移動(dòng)方向：上下左右
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; // 標(biāo)記為已訪問(wèn)while (front < rear) {Point current = dequeue();// 如果到達(dá)終點(diǎn) (n-1, m-1)if (current.x == n - 1 && current.y == m - 1) {return 1; // 可到達(dá)}// 檢查四個(gè)方向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; // 標(biāo)記為已訪問(wèn)enqueue((Point){new_x, new_y}); // 入隊(duì)}}}return 0; // 不可到達(dá)
}int main() {scanf("%d %d", &n, &m);// 讀取迷宮for (int i = 0; i < n; i++) {scanf("%s", maze[i]);}// 如果起點(diǎn)或終點(diǎn)是墻，直接輸出 Noif (maze[0][0] == '#' || maze[n-1][m-1] == '#') {printf("No\n");return 0;}// 執(zhí)行 BFSif (bfs()) {printf("Yes\n");} else {printf("No\n");}return 0;
}