题解 P2407 【[SDOI2009]地图复原】
小菜鸟
2020-01-30 20:09:18
这题...
两篇pascal题解，仅有的cpp题解码风堪忧
所以我来补充个代码（
---
第一眼看到也以为要图论算法
然而仔细观察，我们意识到一个问题：
同一行/列中，转角必定是两两匹配，否则会往一个方向回不去，不能形成环。
然后题面又说保证有解。
那就直接1与2，3与4，5与6匹配就好了...
---
```cpp
#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');
}
}
```