题解 P2407 【[SDOI2009]地图复原】

Marginal_world · 2021-08-04 16:50:41 · 题解

第一眼看到以为是图论。

然而仔细观察，我们意识到一个重要的问题：

同一行/列中，转角必定是两两匹配，否则会往一个方向回不去，不能形成环，这是可以证明的。

然后题面又说保证有解。

我们相信出题人不会自己挖坑自己跳。

所以：

那就直接 1 与 2 ， 3 与 4 ， 5 与 6 匹配就好了...

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[805][805];
bool vis[805][805],lin[805][805];
int main(){
    scanf("%d%d\n",&n,&m);
    for(int i=0;i<n;++i)
    scanf("%s",a[i]);
    for(int i=0;i<n;++i){
        int t=0;
        for(int j=0;j<m;++j){
            if(a[i][j]=='T')t^=1;//使得匹配的两个转角间被标记为1
            lin[i][j]=t;
        }
    }
    for(int j=0;j<m;++j){
        int t=0;
        for(int i=0;i<n;++i){
            if(a[i][j]=='T')t^=1;//同理
            vis[i][j]=t;
        }
    }
    for(int i=0;i<n;++i){//答案每次输出两行，一行为横向路径，一行为纵向路径
        for(int j=0;j<m;++j){
            putchar('o');
            putchar(lin[i][j]?'-':' ');
        }
        if(i==n-1)break;//消除最后一行多余的部分
        putchar('\n');
        for(int j=0;j<m;++j){
            putchar(vis[i][j]?'|':' ');
            putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}

希望能对大家有所帮助。