CF1517C-Fillomino 2
题目大意：给出一个n×n的网格，在它的主对角线上填上n的排列，之后在主对角线的下方填数。要求填的数为x的网格一定要有x个，且在同一个连通块中。
从第一行的主对角线的格子开始，填这个格子所对应的数x，一共要填x个格子。填的规则如下：如果当前格的左边的格子是空着的且不是边界，那么就填到当前格的左边，否则就填到当前格的下面。这样就保证了待填的三角区域左上角的格子都填上了，最大化地利用了空间。按照这种填法，总是可以填完的，不需要输出-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
using namespace std;
int p[505], a[505][505];
const int oprx[] = {0, 1}, opry[] = {-1, 0};
int main()
{
int n, i, j, t;
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &p[i]);
memset(a, 1, sizeof(a));
for (i = 1; i <= n; i++)
{
for (j = 1; j < i; j++)
a[i][j] = 0;
}
for (i = 1; i <= n; i++)
{
a[i][i] = p[i];
int curx = i, cury = i;
for (t = 1; t < p[i]; t++)
{
for (j = 0; j < 2; j++)
{
if (a[curx + oprx[j]][cury + opry[j]] == 0)
{
curx += oprx[j];
cury += opry[j];
a[curx][cury] = p[i];
break;
}
}
if (j >= 2)
break;
}
if (t < p[i])
break;
}
for (i = 1; i <= n; i++)
{
for (j = 1; j <= i; j++)
printf("%d ", a[i][j]);
printf("\n");
}
return 0;
}
|