LGOJ P5461 【赦免战俘】

|

Description

一个 $2^n \times2^n$ 的矩阵，每个位置站着一个作弊者，每次将正方形矩阵 分割 成4个更小的正方形矩阵，每个矩阵的边长是原矩阵的 一半 。其中 左上角 那一个矩阵的所有作弊者都将得到 赦免 ，剩下的三个矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后以 同样的方式 分割矩阵，以同样的方式 赦免 ，直到矩阵不能再分割为止，剩下的作弊者将会被惩罚。求这个矩阵每个作弊者的命运，赦免为 0 ，惩罚为 1 。

$n\leq 10$

Solution

这是 洛谷2019七月月赛 的题目。

这题很快就码出来了，结果我的本地C++跑了四秒多（$n=10$），以为要打表了，结果交上去就直接AC了。想了一下应该是电脑老旧（windows 7的笔记本，装了一大堆的颓废软件）的问题。

考虑使用 DFS（深度优先搜索） 和 分治 来做。

这道题就是求一个按题目描述处理后的矩阵，为了减小码量，我们直接设每个作弊者都要被惩罚，然后每次分割时只需要把4个被分割的正方形矩阵的左上角那个全部设为0即可。

DFS时注意这个矩阵是否不能分割了，那剩下的那名作弊者就就要受到惩罚。

具体细节见 代码 。

code

1
#include<cmath>
2
#include<cstdio>
3
#include<cstring>
4
#include<iostream>
5
#include<algorithm>
6
using namespace std;
7
int ma[1025][1025],n;
8
void dfs(int x1,int y1,int x2,int y2)
9
{
10
    if(x1==x2&&y1==y2)return;
11
    int x3=(x1+x2)/2;
12
    int y3=(y1+y2)/2;
13
    for(int i=x1;i<=x3;i++)
14
    {
15
        for(int j=y1;j<=y3;j++)
16
        {
17
            ma[i][j]=0;
18
        }
19
    }
20
    dfs(x3+1,y1,x2,y3);
21
    dfs(x1,y3+1,x3,y2);
22
    dfs(x3+1,y3+1,x2,y2);
23
}
24
int main()
25
{
26
    scanf("%d",&n);
27
    n=(1<<n);
28
    for(int i=1;i<=n;i++)
29
    {
30
        for(int j=1;j<=n;j++)
31
        {
32
            ma[i][j]=1;
33
        }
34
    }
35
    dfs(1,1,n,n);
36
    for(int i=1;i<=n;i++)
37
    {
38
        for(int j=1;j<=n;j++)
39
        {
40
            printf("%d ",ma[i][j]);
41
        }
42
        printf("\n");
43
    }
44
    return 0;
45
}