电路维修

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1821 字
转成格点图后用 0-1 BFS 求最少旋转
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1448
// 题意：N * M 个方格各有一条对角线导线（\ 或 /），可以旋转任一格改变导线方向，求让左上角电源与右下角灯泡连通的最少旋转次数，无解输出 NO SOLUTION。
// 思路：转化成格点图上的 0-1 BFS。
// 1. 把 (N + 1) * (M + 1) 个格点当结点，穿过一个格子的对角线段看成边。
// 2. 边权为 0 表示导线方向正好连通这两个格点，边权为 1 表示需要把该格旋转一次。
// 3. 边权只有 0 和 1，用双端队列做 0-1 BFS，权 0 放队首、权 1 放队尾。
// 复杂度：O(NM) 时间 / O(NM) 空间
// 易错点：\ 连通的是左上-右下，/ 连通的是左下-右上，判断期望字符时别搞反。
// 易错点：读入的是反斜杠字符，C++ 里要写成 '\\'；题面转义可能让一行变长，只取前 M 个字符。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    vector<string> tile(n);
    for(int i = 0; i < n; i++){
        cin >> tile[i];
        if((int)tile[i].size() > m) tile[i] = tile[i].substr(0, m);
    }
    const int INF = 1e9;
    vector<vector<int>> dist(n + 1, vector<int>(m + 1, INF));
    vector<vector<int>> done(n + 1, vector<int>(m + 1, 0));
    deque<pair<int, int>> dq;
    dist[0][0] = 0;
    dq.push_back({0, 0});
    int dr[4] = {1, 1, -1, -1};
    int dc[4] = {1, -1, 1, -1};
    while(!dq.empty()){
        int r = dq.front().first;
        int c = dq.front().second;
        dq.pop_front();
        if(done[r][c]) continue;
        done[r][c] = 1;
        for(int k = 0; k < 4; k++){
            int nr = r + dr[k], nc = c + dc[k];
            if(nr < 0 || nr > n || nc < 0 || nc > m) continue;
            int tr = min(r, nr), tc = min(c, nc);
            char want = '/';
            if((r == tr && c == tc) || (nr == tr && nc == tc)) want = '\\';
            int w = (tile[tr][tc] == want ? 0 : 1);
            if(dist[r][c] + w < dist[nr][nc]){
                dist[nr][nc] = dist[r][c] + w;
                if(w == 0) dq.push_front({nr, nc});
                else dq.push_back({nr, nc});
            }
        }
    }
    if(dist[n][m] == INF) cout << "NO SOLUTION\n";
    else cout << dist[n][m] << "\n";
    return 0;
}
电路维修

正文

一本通·提高篇的其它内容
