走迷宫

auto ifok = [&que, &mp](int x, int y)->void{que.push(pos(x, y)); mp[x][y] = true;};

import java.util.*;

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

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

    private static boolean[][] visited;

    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[] position = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int n = Integer.parseInt(line[0]);
            int m = Integer.parseInt(line[1]);
            char[][] matrix = new char[n][m];
            visited = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                matrix[i] = in.nextLine().toCharArray();
            }
            int startX = position[0] - 1, startY = position[1] - 1;
            int endX = position[2] - 1, endY = position[3] - 1;

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

            while (!queue.isEmpty()) {
                cur = queue.poll();
                int curX = cur.x;
                int curY = cur.y;
                int curStep = cur.step;

                if (curX == endX && curY == endY) {
                    System.out.println(curStep);
                    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] == '.') {
                        visited[dx][dy] = true;
                        queue.add(new Point(dx, dy, curStep + 1));
                    }
                }
            }

            if (!isArrive) {
                System.out.println(-1);
            }
        }
    }
}

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

from collections import deque
class Maze:
    def __init__(self):
        self.n, self.m = list(map(int, input().split(" ")))
        self.start_y, self.start_x, self.end_y, self.end_x = list(
            map(lambda x: int(x)-1, input().split(" ")))
        self.grid = [['\0' for _ in range(self.m)]
                     for _ in range(self.n)]
        for i in range(self.n):
            self.grid[i] = list(str(input()))
        self.visited = [[False for _ in range(self.m)]
                        for _ in range(self.n)]
        self.direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    def bfs(self):
        queue = deque([(self.start_x, self.start_y, 0)])
        while queue:
            curr_x, curr_y, curr_len = queue.popleft()
            if self.visited[curr_y][curr_x]:
                continue
            self.visited[curr_y][curr_x] = True
            if (curr_y, curr_x) == (self.end_y, self.end_x):
                return curr_len
            for dx, dy in self.direction:
                nx = curr_x + dx
                ny = curr_y + dy
                if ((0 <= nx < self.m) and
                    (0 <= ny < self.n) and
                        self.grid[ny][nx] == "." and
                        not self.visited[ny][nx]):
                    nl = curr_len+1
                    queue.append((nx, ny, nl))
        return -1
if __name__ == "__main__":
    m = Maze()
    print(m.bfs())

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 [xs, ys, xt, yt] = (await readline()).split(" ").map(Number);
        const mtx = Array(n);

        if (xs === xt && ys === yt) {
            console.log(1);
            continue;
        }

        for (let i = 0; i < n; i++) {
            mtx[i] = (await readline()).split("");
        }

        const visited = Array.from({ length: n }, () => Array(m).fill(false));
        visited[xs-1][ys-1] = true;
        const queue = [[xs - 1, ys - 1]];
        let steps = 0;
        let reachable = false;
        let front = 0
        while (front < queue.length) {
            const levelSize = queue.length - front;
            for (let i = 0; i < levelSize; i++) {
                let [x, y] = queue[front++];
                
                if (x - 1 >= 0 && mtx[x - 1][y] === "." && !visited[x - 1][y]) {
                    if (x - 1 === xt - 1 && y === yt - 1) {
                        reachable = true;
                        steps++;
                        break;
                    }
                    queue.push([x - 1, y]);
                    visited[x-1][y] = true;
                }
                if (x + 1 < n && mtx[x + 1][y] === "." && !visited[x + 1][y]) {
                    if (x + 1 === xt - 1 && y === yt - 1) {
                        reachable = true;
                        steps++;
                        break;
                    }
                    queue.push([x + 1, y]);
                    visited[x+1][y] = true;
                }
                if (y - 1 >= 0 && mtx[x][y - 1] === "." && !visited[x][y - 1]) {
                    if (x === xt - 1 && y - 1 === yt - 1) {
                        reachable = true;
                        steps++;
                        break;
                    }
                    queue.push([x, y - 1]);
                    visited[x][y-1] = true;
                }
                if (y + 1 < m && mtx[x][y + 1] === "." && !visited[x][y + 1]) {
                    if (x === xt - 1 && y + 1 === yt - 1) {
                        reachable = true;
                        steps++;
                        break;
                    }
                    queue.push([x, y + 1]);
                    visited[x][y+1] = true;
                }
            }

            if (reachable) {
                break;
            }

            steps++;
        }

        console.log(reachable ? steps : -1);
    }
})();

边界条件放前面

import java.util.*;

public class Main {
    public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int sizeX = in.nextInt();
        int sizeY = in.nextInt();

        int startX = in.nextInt() - 1;
        int startY = in.nextInt() - 1;
        int endX = in.nextInt() - 1;
        int endY = in.nextInt() - 1;

        in.nextLine();
        char[][] graph = new char[sizeX][sizeY];
        for(int i = 0; i < sizeX; i++) {
            String tmp = in.nextLine();
            for(int j = 0; j < sizeY; j++) {
                graph[i][j] = tmp.charAt(j);
            }
        }

        int result = bfs(startX, startY, endX, endY, graph, sizeX, sizeY);

        System.out.println(result);
    }

    private static int bfs(int startX, int startY, int endX, int endY, char[][] graph, int sizeX, int sizeY) {
        if(graph[startX][startY] == '*' || graph[endX][endY] == '*') {
            return -1;
        }

        boolean[][] visited = new boolean[sizeX][sizeY];
        Queue<int[]> queue = new LinkedList<>();
        int step = 0;

        queue.offer(new int[]{startX, startY, step});
        visited[startX][startY] = true;

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0];
            int curY = cur[1];
            int curStep = cur[2];

            if(curX == endX && curY == endY) {
                return curStep;
            }

            for(int[] temp : DIRECTIONS) {
                int newX = curX + temp[0];
                int newY = curY + temp[1];

                if(newX < sizeX && newX >= 0 && newY < sizeY && newY >=0 && visited[newX][newY] == false && graph[newX][newY] != '*') {
                    queue.offer(new int[]{newX, newY, curStep + 1});
                    visited[newX][newY] = true;
                    step++;
                }               
            }
        }

        return -1;
    }
}

from collections import deque

n,m = map(int , input().split())
xs,ys,xt,yt = map(int, input().split())
xs,ys,xt,yt = xs-1,ys-1,xt-1,yt-1
maze = []
for _ in range(n):
    row = list(input())
    maze.append(row)

def play_maze(n,m,xs,ys,xt,yt,maze):
    visited= [[False]*m for _ in range(n)]
    visited[xs][ys]=True
    q = deque()
    q.append((xs,ys,0)) # x,y,steps
    directions = [(1,0),(-1,0),(0,1),(0,-1)]
    while q:
        x,y,steps = q.popleft()
        if (x,y)==(xt,yt):
            return steps
        for dx,dy in directions:
            nx ,ny = x+dx, y+dy
            if 0<=nx<n and 0<=ny<m and maze[nx][ny]=='.' and not visited[nx][ny]:
                visited[nx][ny]=True
                # 注意这里不能写steps +=1,再append(steps),会导致不同方向之间的初始steps会不同
                q.append((nx,ny,steps+1))
    return -1

print(play_maze(n,m,xs,ys,xt,yt,maze)) 

import sys
from collections import deque


def main():
    n, m = map(int, sys.stdin.readline().split())
    xs, ys, xt, yt = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(n)]

    # 转换为 0-based 或保持 1-based，根据题目要求调整
    xs -= 1
    ys -= 1
    xt -= 1
    yt -= 1

    if grid[xs][ys] == "*"&nbs***bsp;grid[xt][yt] == "*":
        print(-1)
        return

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited = [[-1 for _ in range(m)] for __ in range(n)]
    q = deque()
    q.append((xs, ys))
    visited[xs][ys] = 0

    while q:
        x, y = q.popleft()
        if x == xt and y == yt:
            print(visited[x][y])
            return
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if (
                0 <= nx < n
                and 0 <= ny < m
                and grid[nx][ny] == "."
                and visited[nx][ny] == -1
            ):
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))

    print(-1)


if __name__ == "__main__":
    main()

import sys
from collections import deque

try:
    while True:
        n, m = map(int, sys.stdin.readline().split())

        start_x, start_y, end_x, end_y = map(int, sys.stdin.readline().split())

        grid = []
        for _ in range(n):
            line = sys.stdin.readline().strip()
            grid.append(line)

        direction = [(1,0), (0, 1), (-1, 0), (0 , -1)]
        visited = [[False] * m for _ in range(n)]
        queue = deque()
        queue.append((start_x - 1, start_y - 1, 0))
        visited[start_x - 1][start_y - 1] = True
        find_result = False
        while queue:
            x, y, step = queue.popleft()
            if x == end_x - 1 and y == end_y - 1:
                print(step)
                find_result = True

            else:
                for dx, dy in direction:
                    next_x, next_y = dx + x, dy + y
                    if 0 <= next_x < n and 0 <= next_y < m and grid[next_x][next_y] != "*" and not visited[next_x][next_y]:
                        visited[next_x][next_y] = True
                        queue.append((next_x, next_y, step + 1))

        if not find_result:
            print(-1)

except:
    pass

from copy import copy
import copy
def bfs(a1,b1,a2,b2,pathmap):
    queue=[[a1,b1]]
    step=0
    while queue:
        queue1=[]
        for item in queue:
            for i, j in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                if (0<=item[0]+i<=len(pathmap)-1)&(0<=item[1]+j<=len(pathmap[0])-1):
                    a=item[0]+i;b=item[1]+j
                    if (pathmap[a][b]!=1)&(pathmap[a][b]!=-1):
                        queue1.append([a,b])
                        pathmap[a][b]=1
                    if (a==a2)&(b==b2):
                        return step+1

        step+=1
        queue=copy.deepcopy(queue1)
    return -1

n,m=map(int,input().split())
a1,b1,a2,b2=map(int,input().split())
map=[]
for _ in range(n):
    map.append(list(input()))
pathmap=[]
for i in range(n):
    temp=[]
    for j in range(m):
        if map[i][j]=='.':
            temp.append(0)
        else:
            temp.append(-1)
    pathmap.append(temp)

if (pathmap[a2-1][b2-1]==-1)|(pathmap[a1-1][b1-1]==-1):
    short=-1
else:
    pathmap[a1 - 1][b1 - 1] = 1
    short=bfs(a1-1,b1-1,a2-1,b2-1,pathmap)
print(short)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct {
    int x;
    int y;
}node; //坐标系

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int bfs(char** map,int xs,int ys,int xt, int yt,int n,int m){
    int f=0,r=0;
    int dist[n+1][m+1];
    node q[(n+1)*(m+1)];
    for (int i=0;i<n+1;i++) {
         for(int j=0;j<m+1;j++) {
               dist[i][j]=-1;
         }
    }
    q[r].x=xs,q[r].y=ys;
    dist[q[r].x][q[r].y]=0,r++;
    while (f<r) {
         int x=q[f].x,y=q[f].y;
         if (x==xt&&y==yt) {
             return dist[q[f].x][q[f].y];
         }
         else{
            for (int i=0; i<4; i++) {
                 int nx=x+dx[i],ny=y+dy[i];
                 if (nx<=n&&ny<=m&&nx>=1&&ny>=1&&map[nx][ny]=='.'&&dist[nx][ny]==-1) {
                       dist[nx][ny]=dist[q[f].x][q[f].y]+1;
                       q[r].x=nx,q[r].y=ny,r++;
                 }
            }
         }
         f++;
    }
    return -1;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int xs, ys, xt, yt;
    scanf("%d %d %d %d", &xs, &ys, &xt, &yt);
    getchar();
    char** map=(char**)malloc(sizeof(char*)*(n+1));
    for (int i=0; i<n+1; i++) {
           map[i]=(char*)malloc(sizeof(char)*(m+1));
    }
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;j++){
            scanf("%c",&map[i][j]);
        }
        getchar();
    }
    if (map[xt][yt]=='*') {
        printf("-1");
    }
    else {
        printf("%d",bfs(map,xs,ys,xt,yt,n,m));
    }
    return 0;
}