迷宫寻路

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            char[][] map = new char[a+2][b+2];//地图外围一圈边界，避免数组越界
            for(int i = 1; i < a+1; i++){
                String str = in.next();
                for(int j = 1; j < b+1; j++){
                    map[i][j] = str.charAt(j-1);
                }
            }
            System.out.println(method(1,1,map,a,b) ? "Yes" : "No");
        }
    }
    public static boolean method(int ia,int ib,char[][] map,int a,int b){//a,b代表终点
        map[ia][ib] = '#';//标记走过的点
        if(ia == a && ib == b){return true;}//到达终点
        if(map[ia][ib-1] == '.'){if (method(ia,ib-1,map,a,b)) return true;}//向上走
        if(map[ia][ib+1] == '.'){if (method(ia,ib+1,map,a,b)) return true;}//向下走
        if(map[ia-1][ib] == '.'){if (method(ia-1,ib,map,a,b)) return true;}//向左走
        if(map[ia+1][ib] == '.'){if (method(ia+1,ib,map,a,b)) return true;}//向右走
        return false;
    }
}

n , m = map(int,input().split())
arr = []
for i in range(n):
    arr.append(list(input()))
graph = {}
for i in range(n):
    for j in range(m):
        if arr[i][j] == ".":
            graph[(i,j)] = []
            if i - 1 >= 0 and arr[i-1][j]==".":
                graph[(i,j)].append((i-1,j))
            if j - 1 >= 0 and arr[i][j-1]==".":
                graph[(i,j)].append((i,j-1))
            if j + 1 <= m - 1 and arr[i][j+1]==".":
                graph[(i,j)].append((i,j+1))
            if i + 1 <= n - 1 and arr[i+1][j]==".":
                graph[(i,j)].append((i+1,j))
# print(graph)
def can_reach(graph, start, target):
    stack = [start]
    visited = set()
    while stack:
        current = stack.pop()
        if current == target:
            return "Yes"
        if current in visited:
            continue
        visited.add(current)
        for neighbor in graph[current]:
            if neighbor not in visited:
                stack.append(neighbor)
    return "No"
print(can_reach(graph,(0,0),(n-1,m-1)))

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static boolean[][] visited;

    private static int[][] direction = new int[][] {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String[] line = in.nextLine().split(" ");
            int n = Integer.parseInt(line[0]);
            int m = Integer.parseInt(line[1]);
            visited = new boolean[n][m];
            char[][] matrix = new char[n][m];
            for (int i = 0; i < n; i++) {
                matrix[i] = in.nextLine().toCharArray();
            }

            Queue<Point> queue = new LinkedList<>();
            queue.add(new Point(0, 0));
            visited[0][0] = true;
            boolean isArrive = false;

            Point cur = null;
            while (!queue.isEmpty()) {
                cur = queue.poll();

                // 到达终点，直接返回
                if (cur.x == n - 1 && cur.y == m - 1) {
                    System.out.println("Yes");
                    isArrive = true;
                    break;
                }

                // 若符合条件，上下左右遍历
                for (int i = 0; i < direction.length; i++) {
                    int dx = cur.x + direction[i][0];
                    int dy = cur.y + direction[i][1];

                    if (dx >= 0 && dx < n && dy >= 0 && dy < m && !visited[dx][dy] && matrix[dx][dy] == '.') {
                        queue.add(new Point(dx, dy));
                        visited[dx][dy] = true;
                    }
                }
            }

            // 到达出口的标志位未改变，说明没有出口
            if (!isArrive) {
                System.out.println("No");
            }
        }
    }
}

class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> maze(n);
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }

    // 起点和终点
    int startX = 0, startY = 0;
    int endX = n - 1, endY = m - 1;

    // 如果起点或终点是墙，直接返回No（但题目保证是空地）
    if(maze[startX][startY] == '#' || maze[endX][endY] == '#') {
        cout << "No" << endl;
        return 0;
    }

    // 方向数组：左、下、右、上
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    // 访问标记数组
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    // BFS队列
    queue<pair<int, int>> qu;
    qu.push({startX, startY});
    visited[startX][startY] = true;
    
    while (!qu.empty()) {
        auto [x, y] = qu.front();
        qu.pop();

        // 到达终点
        if(x == endX && y == endY) {
            cout << "Yes" << endl;
            return 0;
        }

        // 遍历四个方向
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
        
            // 检查新位置是否在迷宫内、是空地、且未访问
            if(nx >= 0 && nx <= endX && ny >=0 && ny <= endY 
            && visited[nx][ny] == false && maze[nx][ny] == '.') {
                qu.push({nx, ny});
                visited[nx][ny] = true;
            }    
        }
        
    }

    // BFS结束仍未到达终点
    cout << "No" << endl;
    return 0;
}

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        const [n, m] = line.split(' ').map(Number);
        const mtx = Array(n);
        for (let i = 0; i < n; i++) {
            mtx[i] = (await readline()).split('');
        }

        const visited = Array.from({length: n}, () => Array(m).fill(false));

        const dfs = function(i, j) {
            if (i < 0 || j < 0 || i >= n || j >= m || visited[i][j] || mtx[i][j] === '#') return false;
            if (i === n-1 && j === m-1) {
                return true;
            }

            visited[i][j] = true;

            if (dfs(i-1, j)) return true;
            if (dfs(i+1, j)) return true;
            if (dfs(i, j-1)) return true;
            if (dfs(i, j+1)) return true;

            return false;
        };

        console.log(dfs(0, 0) ? "Yes" : "No");
    }
}()

#include <iostream>
using namespace std;

int n, m;
int flag = 0;
char map[101][101]; 
bool visited[101][101] = {false};  

void dfs(int x, int y) {

    if (x < 0 || y < 0 || x >= n || y >= m) return;

    if (map[x][y] == '#' || visited[x][y]) return;

    if (x == n - 1 && y == m - 1) {
        flag = 1;
        return;
    }
    visited[x][y] = true;
    dfs(x + 1, y);  
    dfs(x - 1, y);  
    dfs(x, y + 1); 
    dfs(x, y - 1);  
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }

    dfs(0, 0);

    if (flag) cout << "Yes";
    else cout << "No";

    return 0;
}