杭电多校第四场 1012 Last Problem 题解

题目大意

在一个无穷大的画板上，你有n种颜色，编号从1到n，你需要涂第n种颜色，当你涂第i种颜色的时候，他的四周相邻的格子必须有他前面的四种颜色，即n-1到n-4，输出正确的步骤。

解题思路

刚开始的时候看到这个题目，就知道应该是构造，然后递归。

结果我倒推了半天没推出来。

首先你需要涂n，就需要这样。

为了能涂出n-1到n-4，你就需要这样。

你会发现，对于每个灰色的颜色，他们都满足上面的n的颜色分布。

这样，我们就能根据第一张图的颜色分布，构造出正确的涂色的情况了。

只需要dfs出步骤即可。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int mp[2020][2020];

void dfs(int x, int y, int val) {
	if (val <= 0)	return;
	if (mp[x][y - 1] != val - 1)	dfs(x, y - 1, val - 1);
	if (mp[x - 1][y] != val - 2)	dfs(x - 1, y, val - 2);
	if (mp[x + 1][y] != val - 3)	dfs(x + 1, y, val - 3);
	if (mp[x][y + 1] != val - 4)	dfs(x, y + 1, val - 4);
	mp[x][y] = val;
	cout << x <<" "<< y <<" "<< mp[x][y] << endl;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	memset(mp, 0, sizeof(mp));
	dfs(1000, 1000, n);
	return 0;
}