构造题,在 \(n\times n\) 的网格中操作,初始位置在 \((1,1)\),要求输出所有操作。
操作形如 \((k,a_1,a_2,\cdots,a_m)\),表示从之前的位置出发,走 \(k\) 格,到达格子 \(G\)。
然后将格子 \(a_1,a_2,\cdots,a_m\) 删去,应保证其中没有格子 \(G\) 且图仍然联通。
最终要求剩余一个格子。
数据范围 \(1<n\leq 100\),需要保证 \(n\leq k<300\) 且所有 \(k\) 互不相等。
考虑将格子黑白染色,显然走奇数步时将走到不同种颜色的格子上,根据样例可以大胆推测出算法。
考虑将图形标号:
1 | 2 | 3 | 2 | 1 |
---|---|---|---|---|
2 | 3 | 4 | 3 | 2 |
3 | 4 | 5 | 4 | 3 |
2 | 3 | 4 | 3 | 2 |
1 | 2 | 3 | 2 | 1 |
将每次的 \(k\) 设为奇数,那么每次将一定走到奇偶性不同的格子中去,依次从 \(1\sim 4\) 删除即可,同时保证了图的连通性。
最终会停留在格子 \(5\)。
如果 \(n\) 为偶数,就扩充一个,例如当 \(n=4\) 时就用上表的左上角 \(4\times 4\) 代替即可,删除顺序都不变。
实现方面,因为标号还挺难找规律的,所以可以直接 bfs 预处理一下所有标号的格子,然后直接输出即可。
显然我们需要进行 \(n-1\) 步,而 \(101\sim 299\) 也恰好有足够的奇数给我们使用。
所以这个方法的正确性得以证明。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int N = 310;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n;
bool flag, vis[N][N];
vector<pair<int, int> > Move[N];
struct node{int x, y, d;};
queue<node> q;
int read(){
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
int Get(int x, int y){return (x - 1) * (n - flag) + y;}
void Pre_Work(){
for(int i = 1; i < n; i ++) Move[i].clear();
memset(vis, false, sizeof(vis));
q.push((node){1, 1, 1}); vis[1][1] = true;
q.push((node){1, n, 1}); vis[1][n] = true;
q.push((node){n, 1, 1}); vis[n][1] = true;
q.push((node){n, n, 1}); vis[n][n] = true;
while(!q.empty()){
node u = q.front(); q.pop();
Move[u.d].push_back(MP(u.x, u.y));
if(u.d == n - 1) continue;
for(int i = 0; i < 4; i ++){
int x = u.x + dx[i];
int y = u.y + dy[i];
if(x < 1 || x > n || y < 1 || y > n || vis[x][y]) continue;
vis[x][y] = true;
q.push((node){x, y, u.d + 1});
}
}
}
int main(){
n = read();
if(!(n & 1)) flag = true, n ++;
else flag = false;
Pre_Work();
for(int i = 1; i < n; i ++){
printf("%d", n + (i - 1) * 2);
for(int j = 0; j < Move[i].size(); j ++){
int x = Move[i][j].X;
int y = Move[i][j].Y;
if(!flag || (flag && x < n && y < n)) printf(" %d", Get(x, y));
}
puts("");
}
return 0;
}