2016蓝桥杯C/C++省赛B组第6题 方格填数 DFS

方格填数


如下的10个格子
   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+


（如果显示有问题，也可以参看【图1.jpg】）


填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）


一共有多少种可能的填数方案？


请填写表示方案数目的整数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

这个题其实跟经典DFS问题八皇后没什么本质上的区别，注意下左上和右下的两个缺口的处理，不要越界就可以了

#include <cstdio>
#include <queue>
#include <map>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

const int r = 3, c = 4;
int mapp[10][10];
int numv[15];
int cou;

int dir[4][2] = { 0, -1, -1, -1, -1, 0, -1, 1 };

bool check(int x, int y, int n) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
			//相邻的点有相邻的数字
			//还没有填过数字的格子-10 肯定不会等于当前格子0-9 +1或-1
			if (mapp[nx][ny] == n - 1 || mapp[nx][ny] == n + 1) {
				return false;
			}
		}
	}
	return true;
}

void dfs(int dep, int pos) {

	//(2,3)为缺口，结束
	if (dep == 2 && pos == 3) {
		cou++;
#if 0
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				printf("%4d", mapp[i][j]);
			}
			puts("");
		}
		puts("");
		system("pause");
#endif
		return;
	}

	if (pos >= c) {
		dfs(dep + 1, 0);
	}
	else {
		for (int i = 0; i <= 9; i++) {
			//这个数i没用过，并且没有越出格子
			if (!numv[i] && check(dep, pos, i)) {
				numv[i] = true;
				mapp[dep][pos] = i;
				dfs(dep, pos + 1);
				mapp[dep][pos] = -10;
				numv[i] = false;
			}
		}
	}
}

int main()
{
	//初始化为一个比较大的负数，那么在
	for (int i = 0; i <= 5; i++) {
		for (int j = 0; j <= 5; j++) {
			mapp[i][j] = -10;
		}
	}
	memset(numv, false, sizeof(numv));
	cou = 0;
	dfs(0, 1); //(0,0)为缺口，所以从(0,1)开始
	cout << cou << endl;  //1580
	return 0;
}