BZOJ4148【AMPPZ2014】Pillars <构造>

Problem

【AMPPZ2014】Pillars

Time Limit: $5 Sec$
Memory Limit: $256 MB$
$Special\;Judge$

Description

给定一个$n\times m$的矩形，其中有f个$2\times 2$的障碍物，其中任意两个障碍物中心之间的欧几里得距离至少为$6$，
且每个障碍物的中心到边缘的距离至少为$3$。请找到一条从左下角$(1,1)$出发经过所有没有障碍物的点各一次的且最后回到左下角的回路。

Input

第一行包含三个整数$n,m,f$($1\le n,m\le 1000$且$n,m$都为偶数)。
接下来$f$行，每行两个整数$x,y$($1\le x<n$, $1\le y<m$)，表示该障碍物左下角的坐标。

Output

如果无解，输出$NIE$，否则第一行输出$TAK$，第二行输出方案。
方案包含$n\times m-4\times f$个字符，第$i$个字符表示第$i$步的移动方向，用$G$表示上，$D$表示下，$L$表示左，$P$表示右。

Sample Input

12 6 2
3 3
9 3

Sample Output

TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD

Hint


标签：构造

Solution

一道很适合构造入门的题。
我看了$Claris$的题解才想出来。
首先不考虑障碍，构造出一个走过全部格子的走法。由于$n$和$m$均为偶数，一定有解。
然后考虑障碍，对障碍四周的格子的方向进行修改。由于两个障碍间距离至少为$3$，故任两个障碍不会影响，只会有两大类。
具体构造方法参见代码。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
using namespace std;
int n, m, f;    char s[MAX_N+5][MAX_N+5];
int main() {
    scanf("%d%d%d", &n, &m, &f);
    for (int i = 1; i <= n; i++)	for (int j = 1; j <= m; j++)	s[i][j] = i&1 ? 'D' : 'G';
    for (int i = 1; i <= n; i++) {
        if (i^n)	s[i][1] = 'P';
        if ((i^1) && (i&1))	s[i][2] = 'L';
        if (!(i&1))	s[i][m] = 'L';
    }
    for (int i = 0; i < f; i++) {
        int x, y;	scanf("%d%d", &x, &y);
        if (x&1)	s[x][y+2] = 'P', s[x+1][y-1] = 'L', s[x+1][y+2] = 'P', s[x+2][y+3] = 'L';
        else if (y^3)	s[x][y-1] = 'P', s[x+1][y-1] = 'P', s[x+1][y+2] = 'L', s[x+2][y-2] = 'L';
        else	s[x][1] = 'G', s[x][2] = 'P', s[x+1][2] = 'D', s[x+1][5] = 'L';
    }
    puts("TAK");
    for (int x = 1, y = 1, lft = n*m-4*f; lft; lft--) {
        putchar(s[x][y]);
        if (s[x][y] == 'P')	x++;
        else if (s[x][y] == 'L')	x--;
        else if (s[x][y] == 'G')	y++;
        else	y--;
    }
    return 0;
}