洛谷P2407 [SDOI2009]地图复原
? 解题记录 ? ? 洛谷 ? ? 模拟 ?    2018-10-29 23:17:40    635    0    0

题目描述

很久以前,有一个传说中的“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)。

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

 

输入输出样例

输入样例#1: 复制
3 4
TST.
S.TT
TSST
输出样例#1: 复制
o-o-o o
|   |  
o o o-o
|     |
o-o-o-o

说明

对于20%的数据,有N ≤ 10;

对于40%的数据,有1 ≤ N, M ≤ 80;

对于40%的数据,输入没有“.”,且N, M > 10;

对于100%的数据,满足1 ≤ N, M ≤ 800。

第一眼感觉是神奇建图的哈密尔顿回路,但是一想到哈密尔顿回路是npc的就打消了这种想法。

然后发现智商下线了,实际上如果一定有解的话,有一种很简单的构造方式。直接横行把T两两配对,纵行把T两两配对,S直接连就可以了。

怕是做题做傻了

#include<cstdio>
using namespace std;
const int maxn = 805;
int n, m, last;
char mp[maxn][maxn];
int D[maxn][maxn], R[maxn][maxn];

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; ++i)
        scanf("%s", mp[i] + 1);
    for(register int i = 1; i <= n; ++i) {
        last = 0;
        for(register int j = 1; j <= m; ++j)
            if(mp[i][j] == 'T') 
                if(last) {
                    for(register int k = last; k <= j - 1; ++k)
                        R[i][k] = 1;
                    last = 0;
                }
                else last = j;
    }
    for(register int i = 1; i <= m; ++i) {
        last = 0;
        for(register int j = 1; j <= n; ++j)
            if(mp[j][i] == 'T') 
                if(last) {
                    for(register int k = last; k <= j - 1; ++k)
                        D[k][i] = 1;
                    last = 0;
                }
                else last = j;
    }
    for(register int i = 1; i <= n; ++i) {
        for(register int j = 1; j <= m; ++j) {
            putchar('o');
            if(R[i][j]) putchar('-');
            else putchar(' ');
        }
        if(i == n) break;
        putchar('\n');
        for(register int j = 1; j <= m; ++j) {
            if(D[i][j]) putchar('|');
            else putchar(' ');
            putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}


上一篇: 洛谷P3847 [TJOI2007]调整队形

下一篇: 洛谷P1841 [JSOI2007]重要的城市

635 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航