SGU109 Magic of David Copperfield II

Magic of David Copperfield II

构造题,在 \(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;
}
上一篇:第四章 kotlin其他基础知识1


下一篇:Python——递归函数