陷阱迷宫

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
#include<climits>

using namespace std;

// 构建小根堆
struct Node {
    int cost;
    int i;
    int j;
    bool operator<(const Node& other) const{
        return cost > other.cost;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<char>> grid(n, vector<char>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    vector<vector<int>> visited(n, vector<int>(n, INT_MAX));
    visited[0][0] = 0;
    if (grid[n - 1][n - 1] == '1') {
        cout << "No solution\n";
        return 0;
    }
    priority_queue<Node> pq;
    pq.push({0, 0, 0});
    while (!pq.empty()) {
        auto [cost, i, j] = pq.top();
        pq.pop();
        if (cost > visited[i][j]) {
            continue;
        }
        for (auto dir : dirs) {
            int di = i + dir[0];
            int dj = j + dir[1];
            if (di < 0 || dj < 0 || di >= n || dj >= n || grid[di][dj] == '1') {
                continue;
            }
            int newCost = cost + 1;
            if (grid[di][dj] == '#') {
                newCost += k;
            }
            if (visited[di][dj] > newCost) {
                pq.push({newCost, di, dj});
                visited[di][dj] = newCost;
            }
        }
    }
    if (visited[n - 1][n - 1] == INT_MAX) {
        cout << "No solution\n";
    }
    else {
        cout << visited[n - 1][n - 1] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

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


```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);
    }
}