算法1

(BFS) $O(n^2)$

JAVA 代码

import java.util.*;

class Elem{
    int x;
    int y;
    public Elem(){

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

public class Main{
    static final int N = 110;
    static int[][] g = new int[N][N];//存储地图
    static int[][] d = new int[N][N];//标记搜索到点到原点的位置
    static int n , m;//地图的长宽
    static Queue<Elem> queue = new LinkedList<>();

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                g[i][j] = sc.nextInt();
            }
        }
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                d[i][j] = -1;
            }
        }
        d[0][0] = 0;
        System.out.println(bfs());
    }

    public static int bfs(){
        Elem elem = new Elem(0,0);
        queue.add(elem);

        int[] dx = {-1,0,1,0};
        int[] dy = {0,-1,0,1};
        while(!queue.isEmpty()){
            Elem j = queue.poll();
            for(int i = 0 ; i < 4 ; i++){
                int x = j.x + dx[i];
                int y = j.y + dy[i];
                if(x >= 0 && y >= 0 && x < n && y < m && g[x][y] == 0 && d[x][y] == -1){
                    d[x][y] = d[j.x][j.y] + 1;
                    queue.add(new Elem(x,y));
                }
            }
        }
        return d[n-1][m-1];
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla