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

小菜鸟 · 2020-01-30 20:09:18 · 题解

这题...

两篇pascal题解，仅有的cpp题解码风堪忧

所以我来补充个代码（

第一眼看到也以为要图论算法

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

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

然后题面又说保证有解。

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

#include<cstdio>
#include<algorithm>

int n,m;
char a[805][805];
bool col[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;//同理
            col[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(col[i][j]?'|':' ');
            putchar(' ');
        }
        putchar('\n');
    }
}