算法分析

由于题目要求输出从(0,0)到(n - 1,n - 1)的最短距离的路径

• 1、从(n - 1,n - 1)点通过bfs找到每一个点到(n - 1,n - 1)点的最短距离dist[i][j]

• 2、从(0,0)点开始出发，通过bfs层层遍历，每个点遍历四周点若dist[x][y] == dist[a][b] + 1，则表示(x,y)点到(n - 1,n - 1)点的最短距离是由(a,b)转移过来的，赋值为x = a,y = b

时间复杂度 $O(n^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int N = 1010;
    static int n;
    static int[][] g = new int[N][N];
    static int[][] dist = new int[N][N];
    static int[] dx = new int[] {-1,0,1,0};
    static int[] dy = new int[] {0,1,0,-1};
    static void bfs()
    {
        Queue<PIIs> q = new LinkedList<PIIs>();
        q.add(new PIIs(n - 1,n - 1));
        for(int i = 0;i < n;i ++) Arrays.fill(dist[i], -1);
        dist[n - 1][n - 1] = 0;
        while(!q.isEmpty())
        {
            PIIs t = q.poll();
            for(int i = 0;i < 4;i ++)
            {
                int a = t.x + dx[i];
                int b = t.y + dy[i];
                if(a < 0 || a >= n || b < 0 || b >= n) continue;
                if(dist[a][b] != -1) continue;
                if(g[a][b] == 1) continue;

                dist[a][b] = dist[t.x][t.y] + 1;
                q.add(new PIIs(a,b));
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine().trim());
        for(int i = 0;i < n;i ++)
        {
            String[] s1 = reader.readLine().split(" ");
            for(int j = 0;j < n;j ++)
            {
                g[i][j] = Integer.parseInt(s1[j]);
            }
        }
        bfs();
        int x = 0,y = 0;
        System.out.println(0 + " " + 0);
        while(x != n - 1 || y != n - 1)
        {
            for(int i = 0;i < 4;i ++)
            {
                int a = x + dx[i];
                int b = y + dy[i];
                if(a < 0 || a >= n || b < 0 || b >= n) continue;
                if(dist[x][y] == dist[a][b] + 1)
                {
                    System.out.println(a + " " + b);
                    x = a;
                    y = b;
                    break;
                }
            }
        }
    }
}
class PIIs
{
    public int x;
    public int y;
    public PIIs(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}