Codeforces 293B

Codeforces 293B

原题
题目描述：给出一个(n imes m)的网格， 给定一个整数(k)，网格上的每个数都不超过(k)，其中有的格子是(0)，要求把这些格子变成(1~k)的其中一个数， 使得任一条从左上角到右下角的路径中的数字都不一样， 求方案数。

solution
一开始看到题目的范围这么大，瞬间就懵了，但发现(k leq 10)， 所以就可以搜索+剪枝了。主要的剪枝是最小表示法，就是当某个数字在我当前的搜索中第一次出现，那就记住这次搜索的答案， 若有其他数字也是第一次出现时， 直接取该答案。

code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
using namespace std;

const int maxn=int(1e5)+100;

int n, sum;
int route[maxn];
bool vis[maxn];

void dfs(int cur)
{
	if (vis[cur]) return;
	vis[cur]=true;
	dfs((cur*2)%n);
	dfs((cur*2+1)%n);
	route[++sum]=cur;
}
void solve()
{
	dfs(0);
	for (int i=sum; i>0; --i) printf("%d ", route[i]);
	printf("0
");
}
int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	scanf("%d", &n);
	if (n & 1) printf("-1
");
	else solve();
	return 0;
}