Luogu-P2407-地图复原

Posted on Edited on Word count in article: 1k

题目 P2407 [SDOI2009] 地图复原

题目描述

很久以前，有一个传说中的“EWF”部族，他们世代生活在一个N×M的矩形大地上。虽然，生活的地区有高山、有沼泽，但通过勤劳勇敢，渐渐地，他们在自己的地盘上修筑了一条回路。

后来，“EWF”部族神秘地消失了。不过，考古学家在那片他们曾经生活过的地方找到了一份地图。地图是N×M的矩阵，左上角的坐标为(0, 0)，右下角的坐标为(N, M)。矩阵中的每个格子，表示高山、沼泽、平地、房屋或是道路其中之一。如果一个格子表示道路，那么经过这个格子的道路要么是直走，要么是拐弯。如下图，左边2幅表示直走格子的，右边4幅表示需要拐弯的格子。一个表示道路的格子只能表示下列情况之一。

示意图片

可是，由于地图的年代久远，考古学家虽然能分清一个格子代表的地形，可对于道路的标记，考古学家们只能分清这一格是表示直走的还是拐弯的。现在，他们求助于你，希望你能帮助他们复原这份“EWF”部族的地图。

输入格式

输入文件recover.in的第一行包含两个用空格分隔的正整数N和M，分别表示地图的高和长。

接下来一个N行M列的矩阵描述地图，矩阵中没有多余字符。

大写“S”表示直走的道路，大写“T”表示拐弯的道路，点“.”表示高山、沼泽、平地和房屋。

输出格式

输出文件recover.out包含2N-1行，每行2M-1个字符，描述了这条回路。

所有第2i+1行的2j+1个字符为小写字母o，表示了矩阵的第i行第j列的格子的中心(i, j)。

若回路包含了(i, j)到(i, j+1)或(i, j+1)到(i, j)的一条路径，则第2i+1行的第2j+2个字符为减号“-”（ASCII码为45）；

若回路包含了(i, j)到(i+1, j)或(i+1, j)到(i, j)的一条路径，则第2i+2行的第2j+1个字符为竖线“|”（ASCII码为124）。

其它以上未说明位置上的字符为空格（ASCII码为32）。

输入数据保证至少存在一个合法解，故你的输出应有且仅有一条回路。如果存在多组答案，请输出任意一组。

思路：模拟

对T转弯和S直路的处理

此题有一个特殊的性质：

有且仅有一条回路。

也就是说，不能有开放（突出去，不连接别的路）的路。

要保证这条性质成立，应满足以下要求：

  • 一个T转弯能向左连，当且仅当左边共有偶数个T转弯。
    • 若左边有 00 个T转弯，那么这个T转弯一定向右。
    • 若左边有 11 个T转弯，那么这个T转弯一定向左与左边的T转弯配对。
    • …
  • 一个T转弯能向下连，当且仅当上边共有偶数个T转弯，理由同上。
  • 对于一个S直路，方向取决于周围T转弯的状态。

实现方式

  • 对于T转弯的处理：
    • 使用一个数组 col[x]col[x] 记录 xx 位置是否有向下的T转弯。
    • 使用一个变量 rowrow 记录一行内T转弯的数量的奇偶。
    • 每遇到一个T转弯，row ^= 1;，col[i] ^= 1;
    • 根据 rowrow 的值，决定是否向右连接路（左边的路已经由上一个T/S处理）。
  • 对于S直路的处理：
    • 根据 rowrow 的值，决定是否向右连接路（左边的路已经由上一个T/S处理）。
  • 对于跨行路的处理：
    • 根据 col[i]col[i] 的值，决定是否向下连接路（上边的路已经由上一个T/S处理）。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(int &t, int other) {
    t = min(t, other);
}

inline void maxset(int &t, int other) {
    t = max(t, other);
}

const int inf = 0x7f7f7f7f;

const int N = 810;
const int M = 810;

bool col[M], row = false;

char matrix[N][M];

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

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) { // pos in line
            char c = matrix[i][j];
            bool right = false;
            switch(c) {
                case '.':
                    break;
                case 'S':
                    right = row;
                    break;
                case 'T':
                    row ^= 1;
                    right = row;
                    col[j] ^= 1;
                    break;
            }
            cout << 'o' << (right ? '-' : ' ');
        }
        cout << endl;
        for(int j = 1; j <= m; j++) {
            cout << (col[j] ? '|' : ' ') << ' ';
        }
        cout << endl;
    }
    return 0;
}