P7185 题解

rainygame · 2023-11-11 15:41:19 · 题解

本题有 O(nm) 的做法。

注意到输入将保证解决方案存在并且是唯一的，所以只需要考虑哪个地方可以放即可。如果它可以放在这个位置，那么它肯定会被放。

那么只需要 O(1) 和周围的管道判断即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define up(x, y) (x > 1 && (ch[x-1][y] == '|' || ch[x-1][y] == '+' || ch[x-1][y] == '1' || ch[x-1][y] == '4'))
#define down(x, y) (x < n && (ch[x+1][y] == '|' || ch[x+1][y] == '+' || ch[x+1][y] == '2' || ch[x+1][y] == '3'))
#define left(x, y) (y > 1 && (ch[x][y-1] == '-' || ch[x][y-1] == '+' || ch[x][y-1] == '1' || ch[x][y-1] == '2'))
#define right(x, y) (y < m && (ch[x][y+1] == '-' || ch[x][y+1] == '+' || ch[x][y+1] == '3' || ch[x][y+1] == '4'))

int n, m;
char ch[26][26];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i(1); i<=n; ++i){
        for (int j(1); j<=m; ++j) cin >> ch[i][j];
    }

    for (int i(1); i<=n; ++i){
        for (int j(1); j<=m; ++j){
            if (ch[i][j] != '.') continue;
            if (up(i, j) && down(i, j) && left(i, j) && right(i, j)) cout << i << ' ' << j << " +";
            else if (right(i, j) && left(i, j)) cout << i << ' ' << j << " -";
            else if (up(i, j) && down(i, j)) cout << i << ' ' << j << " |";
            else if (down(i, j) && right(i, j)) cout << i << ' ' << j << " 1";
            else if (up(i, j) && right(i, j)) cout << i << ' ' << j << " 2";
            else if (up(i, j) && left(i, j)) cout << i << ' ' << j << " 3";
            else if (down(i, j) && left(i, j)) cout << i << ' ' << j << " 4";
        }
    }

    return 0;
}