最短路

多元最短路[华为]

题目描述：

A可以从上下左右跳一格到C，求所有A的路径总和；
案例：
输入：
3
A B C
A A A
A A C
输出：
13

解释：

4 0 0

3 2 1

2 1 0

public class Main {
    static int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] g = new char[n][n];
        boolean[][] vis = new boolean[n][n];
        int[][] res = new int[n][n];
        int ans = 0;
        Queue<int[]> que = new LinkedList<>();

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                g[i][j] = sc.next().charAt(0);
                if(g[i][j]=='C'){
                    que.offer(new int[]{i,j});
                    vis[i][j] = true;
                }
            }
        }

        while(!que.isEmpty()){
            int[] node = que.poll();
            for(int[] dir:dirs){
                int dx = node[0]+dir[0];
                int dy = node[1]+dir[1];
                if(dx<0||dx>=n||dy<0||dy>=n
                        || g[dx][dy]!='A'
                        || vis[dx][dy]){
                    continue;
                }
                vis[dx][dy] = true;
                res[dx][dy] = res[node[0]][node[1]]+1;
                ans += res[dx][dy];
                que.offer(new int[]{dx,dy});
            }
        }
        System.out.println(ans);
    }
}