n = int(input())
grid, S_OR = [], []
for i in range(n):
    crow = list(input())
    if 'S' in crow:
        S_OR = [i, crow.index('S')]
    grid.append(crow)


def BFS(grid, S_OR, n):
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    queue = [S_OR]
    visited = [[False for _ in range(n)] for _ in range(n)]
    visited[S_OR[0]][S_OR[1]] = True
    step = 0
    while queue:
        step += 1
        len_queue = len(queue)
        for _ in range(len_queue):
            q = queue.pop(0)
            for _x, _y in zip(dx, dy):
                x, y = (q[0] + _x + n) % n, (q[1] + _y + n) % n
                if not visited[x][y] and grid[x][y] != '#':
                    if grid[x][y] == 'E':
                        return step
                    queue.append([x, y])
                    visited[x][y] = True
    return -1


print(BFS(grid, S_OR, n))

最短路的搜索问题，可用广度优先搜索。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
int main()
{
    int N;
    while(cin>>N)
    {
        vector<string> g(N);
        string line;
        PII st,end;
        for(int i=0;i<N;i++)
        {
            cin>>line;
            for(int j=0;j<N;j++)
            {
                if(line[j]=='S')   st={i,j};
                if(line[j]=='E')    end={i,j};
            }
            g[i]=line;
        }
        //cout<<st.x<<" "<<st.y<<endl;
        queue<PII> q;
        q.push(st);
        int cnt=0;
        bool vis[N][N];
        memset(vis,0,sizeof vis);
        int dirs[5]={1,0,-1,0,1};
        vis[st.x][st.y]=true;
        bool flag=false;
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                auto cur=q.front(); q.pop();
                if(cur.x==end.x && cur.y==end.y)
                {
                    cout<<cnt<<endl;
                    flag=true;
                    break;
                }
                for(int k=0;k<4;k++)
                {
                    int ni=cur.x+dirs[k],nj=cur.y+dirs[k+1];
                    if(ni==-1) ni=N-1;
                    else if(ni==N) ni=0;
                    if(nj==-1) nj=N-1;
                    else if(nj==N) nj=0;
                    if(vis[ni][nj] || g[ni][nj]=='#') continue;
                    q.push({ni,nj});
                    vis[ni][nj]=true;
                }
            }
            cnt++;
        }
        if(!flag)
            cout<<-1<<endl;
    }
    return 0;
}

def ans(data):
    s_i = 0
    s_j = 0
    queue = []
    for i in range(len(data)):
        for j in range(len(data)):
            if data[i][j] == 'S':
                s_i = i
                s_j = j
                queue.append((s_i,s_j))
                break
    res = 0
    used = [[0]*len(data) for i in range(len(data))]
    used[s_i][s_j] = 1
    while queue:
        res += 1
        length = len(queue)
        for k in range(length):
            i,j = queue.pop(0)
            down = (i + 1 + len(data))%len(data)
            up = (i - 1 + len(data))%len(data)
            left = (j - 1 + len(data))%len(data)
            right = (j + 1 + len(data))%len(data)
            chance = [(up,j),(down,j),(i,left),(i,right)]
            for ii,jj in chance:
                if data[ii][jj] == "." and used[ii][jj] == 0:
                    queue.append((ii,jj))
                    used[ii][jj] = 1
                if data[ii][jj] == 'E':
                    return res
    return -1
    
if __name__ =="__main__":
    num = int(input())
    data = []
    for i in range(num):
        data.append(input())
    print(ans(data))
        

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

class Node{
    public int x;
    public int y;
    public int value;
    public Node(int x,int y,int value){
        this.x=x;
        this.y=y;
        this.value=value;
    }
}
public class Main{
    // ------1-------
    static int[]xx=new int[]{0,0,-1,1};
    static int[]yy=new int[]{-1,1,0,0};
    static int sx=0;
    static int sy=0;
    static int ex=0;
    static int ey=0;
    static int n=-1;
    public static void main(String[] args){
        //------2-------
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        sc.nextLine();
        boolean[][]vis=new boolean[n][n];
        char[][] map =new char[n][n];
        for(int i=0;i<n;i++){
            String line=sc.nextLine();
            for(int j=0;j<n;j++){
                map[i][j]=line.charAt(j);
                if(map[i][j]=='S'){ sx=i;sy=j;}
                if(map[i][j]=='E'){ ex=i;ey=j;}
            }
        }
        sc.close();
        if(sx == -1 && sy == -1)     System.out.println("-1");
        if(ex == -1 && ey == -1)     System.out.println("-1");
        int re=bfs(map,vis);// 求最短路径问题
        System.out.println(re);
    }
    // 标准bfs
    public static int bfs(char[][] map, boolean [][]vis){
        Queue <Node> queue=new LinkedList<Node>();
        queue.offer(new Node(sx,sy,0));
        vis[sx][sy]=true;//  sx和sy只是初始的时候用到了
        while(!queue.isEmpty()){
            Node node=queue.poll();
            for(int i=0;i<4;i++){
                int nx=(xx[i]+node.x+n)%n;      //此时用x不行的
                int ny=(yy[i]+node.y+n)%n;
                if(check(map,vis,nx,ny)){ continue; }
                if(nx==ex&&ny==ey){return node.value+1;}
                vis[nx][ny]=true;
                queue.offer(new Node(nx,ny,node.value+1));
            }
        }
        return -1;
    }
    // 判断函数
    public static boolean check(char[][] map,boolean[][]vis,int x,int y){
        if(map[x][y]=='#'||vis[x][y]==true){
            return true;
        }
        return false;
    }
}

//层序遍历，求深度
#include<iostream>
#include<vector>
#include <queue>
using namespace std;
int main()
{
    int n=0;
    cin>>n;
    vector<vector<char>> mp(n,vector<char>(n,0));
    string tmp;
    int x,y;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            cin>>mp[i][j];
           if(mp[i][j]=='S') 
           {
               x=i;
               y=j;
           }
        }
    //获取数据结束
    queue<pair<int, int>> steps;
    steps.push({x,y});
    int res=0;
    int X[]={0,0,1,-1};
    int Y[]={1,-1,0,0};
    bool findE=false;
    while(!steps.empty())
    {
        int sz=steps.size();
        if(sz) res++;
        while(sz--)
        {
            x=steps.front().first;
            y=steps.front().second;
            steps.pop();
            for(int i=0;i<4;i++)
            {
                int x_next=x+X[i];
                int y_next=y+Y[i];
                x_next=x_next>=n?0:(x_next<0?(n-1):x_next);
                y_next=y_next>=n?0:(y_next<0?(n-1):y_next);
                if(mp[x_next][y_next]=='E')
                {
                    findE=true;
                    break;
                }
                if(mp[x_next][y_next]=='.')
                {
                    steps.push({x_next,y_next});
                    mp[x_next][y_next]='#';
                }
            }//方向循环
            if(findE) break;
           
        }//每一层
        if(findE) break;
    }
    if(findE) cout<<res<<endl;
    else cout<<-1<<endl;
    return 0;
}

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int maxn = 10001;
char matrix[maxn][maxn];
bool inq[maxn][maxn] = {false};

int X[4] = {0, 0, 1, -1};
int Y[4] = {1, -1, 0, 0};

struct node
{
    int x, y;
    int step; //从起点S到达该位置的最少步数
}S, E, Node;//S为起点， E为终点， Node为临时结点

bool isValid(int x, int y)
{
    if(matrix[x][y] == '#') return false;
    if(inq[x][y]) return false;
    return true;
}
int BFS(int n)
{
    queue<node> q;
    q.push(S);
    inq[S.x][S.y] = true;
    while(!q.empty())
    {
        node top = q.front();
        q.pop();

        if(top.x == E.x && top.y == E.y)
        {
            return top.step;
        }

        for(int i = 0; i < 4; i++)
        {
            Node.x = (top.x + X[i]) % n;
            Node.y = (top.y + Y[i]) % n;
            if(isValid(Node.x, Node.y))
            {
                Node.step = top.step + 1;
                q.push(Node);
                inq[Node.x][Node.y] = true;
            }
        }
    }
    return -1;
}
int main(){
    int n;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 0; i < n; i++)
        {
            getchar(); //过滤掉每行的换行符
            for(int j = 0; j < n; j++)
            {
                matrix[i][j] = getchar();
                if(matrix[i][j] == 'S')
                {
                    S.x = i;
                    S.y = j;
                    S.step = 0;
                }
                if(matrix[i][j] == 'E')
                {
                    E.x = i;
                    E.y = j;
                }
            }
            matrix[i][n] = 0;
        }

        printf("%d\n", BFS(n));
        memset(inq, 0, sizeof(bool) * n);
        fflush(stdin);
    }

    return 0;
}

分析

使用BFS从开始节点S向外围搜索，通过类似于树的层次级遍历的方法，使用队列queue.deque存储当前层的节点坐标，并逐个取出来再向外层扩展。注意在添加新的节点到队列过程中要设定新节点为‘#’,不然在下一轮的搜索中这个节点会被重复搜索，从而导致在一些case上超时。

from queue import deque

def bfs(matrix, i, j, N):
    length = 0
    que = deque()
    que.append((i, j))
    while que:
        length += 1
        # 遍历当前层的所有节点
        for _ in range(len(que)):
            x, y = que.popleft()
            for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                new_x = (x + dx) % N
                new_y = (y + dy) % N
                if matrix[new_x][new_y] == 'E':
                    return length
                elif matrix[new_x][new_y] != '#':
                    #提前设定为障碍，避免重复访问
                    matrix[new_x][new_y] = '#'
                    que.append((new_x, new_y))
    return -1

def main():
    N = int(input())
    matrix = [[None for _ in range(N)] for _ in range(N)]
    for i in range(N):
        matrix[i] = list(input())

    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 'S':
                return bfs(matrix, i, j, N)
    return -1
print(main())

def getInput():
    s = input().strip()
    n = int(s)
 
    data = []
    for i in range(n):
        s = input().strip()
        data.append(list(s))
 
    return n, data
 
def main(n, data):
    if n < 2:
        return -1
    si = -1
    sj = -1
    for i in range(n):
        for j in range(n):
            if data[i][j] == 'S':
                si = i
                sj = j
                break
        if si != -1:
            break
    data[si][sj] = '#'
 
 
    queue = [[si, sj, 0]]
    while len(queue) > 0:
        i, j, step = queue.pop(0)
        for add_i, add_j in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            next_i = i + add_i
            next_i = adjust(next_i, n)
            next_j = j + add_j
            next_j = adjust(next_j, n)
            if data[next_i][next_j] != '#':
                if data[next_i][next_j] == 'E':
                    return step + 1
                data[next_i][next_j] = '#'
                queue.append([next_i, next_j, step + 1])
    return -1
 
 
def adjust(x, n):
    if x < 0:
        return n - 1
    if x == n:
        return 0
    return x
 
n, data = getInput()
# n = 5
# s = '.#... ..#S. .E###  ..... .....'
# s_list = s.split()
# data = [list(s) for s in s_list]
ans = main(n, data)
print(ans)

//为啥我这么长，别人都短，我怕是个傻子吧
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
 
struct Point{
    int i;
    int j;
    Point(){}
    Point(int _i,int _j):i(_i),j(_j){}
};
 
class Solution{
    public:
       int getMinNum(vector<string> str,vector<bool> visited){
           if(str.size() == 0 || str[0].size() == 0){
               return -1;
           }
           int N = str[0].size();
           //1.找到SE
           int si,sj;
           int ei,ej;
           for(int i=0;i<str.size();i++){
               for(int j=0;j<str[0].size();j++){
                   if(str[i][j] == 'S'){
                       si = i;
                       sj = j;
                   }
                   if(str[i][j] == 'E'){
                       ei = i;
                       ej = j;
                   }
               }
           }
           // 边界 -1,N
           queue<Point> que;
           que.push(Point(si,sj));
           visited[si*N + sj] = true;
           int count = 0;
           bool flag = false;
           while(!que.empty()){
               int len = que.size();
               for(int i=0;i<len;i++){//
                   Point temp = que.front();
                   que.pop();
                   if(temp.i == ei && temp.j == ej){
                       flag =true;
                       break;
                   }
                   //上面 i-1 ,j
                   if(temp.i != 0 && str[temp.i-1][temp.j] != '#' && !visited[(temp.i-1)*N +temp.j]){
                       que.push(Point(temp.i-1,temp.j));
                       visited[(temp.i-1)*N +temp.j] = true;
                   }
                   if(temp.i == 0 && str[N-1][temp.j] != '#' && !visited[(N-1)*N + temp.j]){
                       que.push(Point(N-1,temp.j));
                       visited[(N-1)*N + temp.j] = true;
                   }
                   // 右面 i , j+1
                   if(temp.j != N-1 && str[temp.i][temp.j+1] != '#' && !visited[(temp.i)*N + temp.j+1]){
                       que.push(Point(temp.i,temp.j+1));
                       visited[(temp.i)*N + temp.j+1] = true;
                   }
                   if(temp.j == N-1 && str[temp.i][0] != '#' && !visited[temp.i * N + 0]){
                       que.push(Point(temp.i,0));
                       visited[temp.i * N + 0] = true;
                   }
                   //下面 i+1,j
                   if(temp.i != N-1 && str[temp.i + 1][temp.j] != '#' &&  !visited[(temp.i+1)*N + temp.j]){
                       que.push(Point(temp.i+1,temp.j));
                       visited[(temp.i+1)*N + temp.j] = true;
                       
                   }
                   if(temp.i == N-1 && str[0][temp.j] != '#' && !visited[0*N + temp.j]){
                       que.push(Point(0,temp.j));
                       visited[0*N + temp.j] = true;
                   }
                   //左面 i,j-1
                   if(temp.j != 0 && str[temp.i][temp.j -1] != '#' && !visited[temp.i *N + temp.j-1]){
                       que.push(Point(temp.i,temp.j-1));
                       visited[temp.i *N + temp.j-1] = true;
                       
                   }
                   if(temp.j == 0 && str[temp.i][N-1] != '#' && !visited[temp.i*N + N-1]){
                       que.push(Point(temp.i,N-1));
                       visited[temp.i*N + N-1] = true;
                   }
                    
               }
               if(flag == true){
                   break;
               }
               count++;
           }
           if(que.empty() && flag == false){
               return -1;
           }
           
           return count;
       }
      
};
 
int main(){
    int n;
    cin>>n;
    vector<string> arr;
    string str;
    for(int i=0;i<n;i++){
        cin>>str;
        arr.push_back(str);
    }
    Solution c1;
    vector<bool> visited(arr.size()*arr.size(),false);
    cout<<c1.getMinNum(arr,visited)<<endl;
    return 0;
     
     
}

def f():
    N = int(input())
    ls = []
    for i in range(N):
        ls.append(list(input()))
    flag = [[0]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if ls[i][j] == 'S':
                start = [i,j]
            if ls[i][j] == 'E':
                end = [i,j]
            if ls[i][j] == '#':
                flag[i][j] = 0
    dir = [(1,0),(0,1),(-1,0),(0,-1)]
    flag[start[0]][start[1]] = 1
    xy = [[start[0],start[1]]]
    step = 0
    while xy:
        tmp_ls = []
        for index in xy:
            i,j = index
            for d in dir:
                new_i = i+d[0]
                new_j = j+d[1]
                if new_i==N:new_i = 0
                elif new_i==-1:new_i = N-1
                if new_j == N:new_j = 0
                elif new_j == -1:new_j = N-1
                if [new_i,new_j] == end:
                    return step+1
                if ls[new_i][new_j]!='#' and flag[new_i][new_j]==0:
                    flag[new_i][new_j] = 1
                    tmp_ls.append([new_i,new_j])
        xy = tmp_ls
        step+=1
    return -1
print(f())

迷宫游戏 小红书 golang bfs

看到大家的程序都很繁琐我就放心了。

基本思路就是bfs，将起点放进待处理的队列，每次出队一个元素，将其相邻的可行元素入队。
可以取消 打印生长过程 的注释，当图生长碰到终点，就输出长度，如果知道结束都没有碰到终点则输出-1.

package main

import (
    "fmt"
)

func main() {
    var n int
    var s [2]int
    var in string
    //标记矩阵
    var mapp [][]int
    fmt.Scan(&n)
    for i:=0;i<n;i++{
        fmt.Scan(&in)
        line:=[]int{}
        for j,v:=range in{
            switch v {
            case '.':
                line = append(line, 1)
            case '#':
                line = append(line, 0)
            case 'S':
                s=[2]int{i,j}
                line = append(line, 9)
            case 'E':
                //e=[2]int{i,j}
                line = append(line, 2)
            }
        }
        mapp = append(mapp, line)
    }
    //列数
    w:= len(mapp[0])
    d:=[4][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    //待处理的点的队列
    queue:=[][2]int{s}
    steps,lenz:=1,1
    reachable:=false
    for i:=0;i< len(queue)&&!reachable;i++{
        if i==lenz{
            steps++
            lenz= len(queue)
            //打印生长过程
            //for _,v:=range mapp{
            //    fmt.Println(v)
            //}
            //fmt.Println("-------",steps,"-----")
            //fmt.Println()
        }
        x,y:=queue[i][0],queue[i][1]
        for i:=0;i<4;i++{
            //注意考虑溢出
            xx,yy:=(x+d[i][0]+w)%w,(y+d[i][1]+w)%w
            switch mapp[xx][yy] {
            //可以走的点标记为9
            case 1:
                mapp[xx][yy]=9
                queue = append(queue, [2]int{xx,yy}) 
            //发现终点提前结束
            case 2:
                reachable=true
                break
            }
        }
    }
    if reachable{
        fmt.Println(steps)
    }else {
        fmt.Println(-1)
    }
}

#include <iostream>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <string>
#include <cstring>
#include <cstdio>
#include <set>
#include <cstdio>
#include <fstream>
#include <deque>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <iomanip>
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
const int mod = 1e9 + 7;
const double esp = 1e-5;
const double PI = 3.141592653589793238462643383279;
using namespace std;
const int N = 1e7 + 5;
const int maxn = 1 << 20;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; while (b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % mod; a = a * a % mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
/*void chafen(int l, int r, int k) {//差分函数
    p[l] += k;
    p[r + 1] -= k;
}*/
/*********************************************************/
bool vis[1005][1005];
char a[1005][1005];
int x[4] = { -1,0,1,0 };
int y[4] = { 0,1,0,-1 };
int u1=-1, v1=-1, u2=-1, v2=-1;
int n, m;
struct node {
    int x;
    int y;
    int step;
};

int convert(int num,int n){
    if(num==-1) return  n-1;
    if(num==n)  return 0;
    return num;
}

int bfs() {
    if(u1==-1 || u2==-1)    return -1;
    queue<node> q;
    node p;//起点
    p.x = u1; p.y = v1;
    p.step = 0;
    q.push(p);
    a[u1][v1]='#';
    while (!q.empty()) {
        node p1 = q.front();
        q.pop();
        node t;
        for (int i = 0; i < 4; i++) {
            t.x = p1.x + x[i] ;
            t.x = convert(t.x,n);
            t.y = p1.y + y[i] ;
            t.y = convert(t.y,n);
            t.step = p1.step + 1;
            if (a[t.x][t.y]!='#') {
                if (a[t.x][t.y]=='E')
                    return t.step;
                else a[t.x][t.y]='#';
                q.push(t);
            }
        }
    }
    return -1;
}
int main()
{
    cin >> n ;
    m = n;
    memset(vis, false, sizeof(vis));
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'S') {
                u1 = i;
                v1 = j;
            }
            if (a[i][j] == 'E') {
                u2 = i;
                v2 = j;
            }
        }
    }
    cout << bfs() << endl;
    return 0;
}
/*
5 5
.....
.*.*.
.*S*.
.***.
...T*
*/