P9622 [ICPC2020 Nanjing R] Ah, It's Yesterday Once More 题解

· · 题解

题目大意

要求构造一个 m\times n 的迷宫，1 表示路，0 表示障碍。迷宫中有一群袋鼠，他们随机移动 5\times10^4 次（向上下左右任意方向走一个格子），构造的迷宫要尽可能让他们最终不会走到同一个格子上。迷宫中不能存在循环（一个格子不经过重复点还能走回这个格子），并且必须是联通的。

思路

首先我们要明确，如果有操作是要求我们走到边界或者是障碍物，那么这次操作相当于浪费了（袋鼠不会动）。因此迷宫的路一定是越窄越好，这样就可以尽可能多的浪费操作次数；然后我们还要让迷宫尽可能的长（减少 0 的出现次数），这样可以使袋鼠走到同一个格子更加困难。

分析后可以发现阶梯型的迷宫是最优的（不用回型图是因为浪费太多格子了），在表格里随便画画就得到答案了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<"20 20\n11100011100011101100\n10110110110110110110\n11011011011011011011\n01101101101101101101\n10110110110110110111\n10011011011011011010\n11101101101101101100\n10110110110110110110\n11011011011011011011\n01101101101101101101\n00110110110110110111\n01011011011011011001\n11101101101101101100\n10110110110110110110\n11011011011011011011\n01101101101101101101\n00110110110110110111\n01011011011011011001\n11101101101001101001\n10111000111110111110\n";
    return 0;
}