陷阱迷宫

用广度优先搜索算法可以少走重复的节点，广度优先搜索算法维护一个队列，队列中的每个元素记录的是该节点到起点的距离。用一个变量记录最小距离，当到达终点时和最小距离进行比较并更新。当算法结束后即可得到最小距离。代码实现如下：


```java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(), K = in.nextInt();
        int[][] graph = new int[N][N];
        boolean visited[][] = new boolean[N][N];
        in.nextLine();
        for (int i = 0; i < N; i++) {
            String line = in.nextLine();
            // System.out.println(line);
            for (int j = 0; j < N; j++) {
                if (line.charAt(j) == '0')   graph[i][j] = 1;
                if (line.charAt(j) == '1')   graph[i][j] = -1;
                if (line.charAt(j) == '#')   graph[i][j] = K;
                visited[i][j] = false;
            }
        }

        
        // Arrays.fill(visited, false);

        // 采用广度优先搜索算法，并在搜索过程中记录节点到起点的距离
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] {0, 0, 0});
        visited[0][0] = true;
        int minDis = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], y = current[1], dis = current[2];
            if(x == N-1 && y == N-1){
                minDis = minDis > dis ? dis : minDis;
                continue;
            }
            visited[x][y] = true;
            // System.out.println("x: " + x + ", y: " + y);
            if (x + 1 < N && visited[x + 1][y] == false && graph[x + 1][y] != -1)
                queue.add(new int[] {x + 1, y, dis + graph[x + 1][y]});
            if (x - 1 >= 0 && visited[x - 1][y] == false && graph[x - 1][y] != -1)
                queue.add(new int[] {x - 1, y, dis + graph[x - 1][y]});
            if (y + 1 < N && visited[x][y + 1] == false && graph[x][y + 1] != -1)
                queue.add(new int[] {x, y + 1, dis + graph[x][y + 1]});
            if (y - 1 >= 0 && visited[x][y - 1] == false && graph[x][y - 1] != -1)
                queue.add(new int[] {x, y - 1, dis + graph[x][y - 1]});
        }
        if(minDis == Integer.MAX_VALUE) System.out.println("No solution");
        System.out.println(minDis);
    }
}