电路维修

题目描述

思路

在图上进行广度优先遍历
边权相同，后来的比先来的付出的代价要大，直接从队尾入队
边权只有1， 0两种，0的累计代价要比1的累计代价小，小于等于队列中的其他点的代价，要从对头入队，1的从队尾入队
记录一个vis数组，记录经过此点的最小代价，防止重复走
题目给的是边，我们走的是点，要找到走对应点时的边

代码

#include <cstdio>
#include <queue>
#include <cstring>

int n, m, ans = -1, inf = 0x3f3f3f3f;
char mp[505][505];
int vis[505][505];
struct Node {
    int x, y, z;  // x表示行，y表示列
} node, tmp;
std::deque<Node> q;
int dirx[5] = {0, -1, -1, 1, 1};
int diry[5] = {0, -1, 1, 1, -1};
bool valid(int x, int y) {
    if (x <= 0 || x > n + 1) return false;
    if (y <= 0 || y > m + 1) return false;
    return true;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1);
    memset(vis, 0x3f, sizeof(vis));
    // for (int i = 1; i <= n; ++i) printf("%s\n", mp[i] + 1);
    node.x = 1, node.y = 1, node.z = 0;
    vis[1][1] = 0;
    q.push_back(node);
    while (!q.empty()) {
        tmp = q.front();
        q.pop_front();
        // printf("x:%d y:%d z:%d\n", tmp.x, tmp.y, tmp.z);
        if (tmp.x == n + 1 && tmp.y == m + 1) {
            ans = tmp.z; break;
        }

        node.x = tmp.x + dirx[1];
        node.y = tmp.y + diry[1];
        if (valid(node.x, node.y)) {
            if (mp[tmp.x - 1][tmp.y - 1] == '\\') {
                node.z = tmp.z;
                if (node.z < vis[node.x][node.y]) {
                    vis[node.x][node.y] = node.z;
                    q.push_front(node);
                }
            } else {
                node.z = tmp.z + 1;
                if (node.z < vis[node.x][node.y]) {
                    vis[node.x][node.y] = node.z;
                    q.push_back(node);
                }
            }
        }

        node.x = tmp.x + dirx[2];
        node.y = tmp.y + diry[2];
        if (valid(node.x, node.y)) {
            if (mp[tmp.x - 1][tmp.y] == '/') {
                node.z = tmp.z;
                if (node.z < vis[node.x][node.y]) {
                    vis[node.x][node.y] = node.z;
                    q.push_front(node);
                }
            }
            else {
                node.z = tmp.z + 1;
                if (node.z < vis[node.x][node.y]) {
                    vis[node.x][node.y] = node.z;
                    q.push_back(node);
                }
            }
        }

        node.x = tmp.x + dirx[3];
        node.y = tmp.y + diry[3];
        if (valid(node.x, node.y)) {
            if (mp[tmp.x][tmp.y] == '\\') {
                node.z = tmp.z;
                if (node.z < vis[node.x][node.y]) {
                    vis[node.x][node.y] = node.z;
                    q.push_front(node);
                }
            }
            else {
                node.z = tmp.z + 1;
                if (node.z < vis[node.x][node.y]) {
                    vis[node.x][node.y] = node.z;
                    q.push_back(node);
                }
            }
        }

        node.x = tmp.x + dirx[4];
        node.y = tmp.y + diry[4];
        if (valid(node.x, node.y)) {
            if (mp[tmp.x][tmp.y - 1] == '/') {
                node.z = tmp.z;
                if (node.z < vis[node.x][node.y]) {
                    vis[node.x][node.y] = node.z;
                    q.push_front(node);
                }
            }
            else {
                node.z = tmp.z + 1;
                if (node.z < vis[node.x][node.y]) {
                    vis[node.x][node.y] = node.z;
                    q.push_back(node);
                }
            }
        }
    }
    if (ans == -1) printf("NO SOLUTION");
    else printf("%d", ans);
    return 0;
}