2306.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 58 行

/*  This Code is Submitted by wywcgs for Problem 2306 on 2006-08-07 at 12:09:41 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
int s[9][9];
bool vst[3][9][10];
 
bool set(int, int, int, bool);
bool find(int, int);
 
int main()
{
	int i, j, t, T;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		memset(vst, false, sizeof(vst));
		for(i = 0; i < 9; i++)
			for(j = 0; j < 9; j++) {
				scanf("%1d", &s[i][j]);
				if(s[i][j] != 0) set(i, j, s[i][j], true);
			}
		printf("Scenario #%d:\n", t);
		find(0, 0);
	}
}
 
bool set(int x, int y, int v, bool p)
{
	int r = x/3, c = y/3, cd = r*3+c;
	if(vst[0][x][v] == p || vst[1][y][v] == p || vst[2][cd][v] == p) return false;
	vst[0][x][v] = vst[1][y][v] = vst[2][cd][v] = p;
	return true;
}
bool find(int x, int y)
{
	int i, j;
	if(x == 9) {
		for(i = 0; i < 9; i++) {
			for(j = 0; j < 9; j++) printf("%d", s[i][j]);
			putchar('\n');
		}
		putchar('\n');
		return true;
	} else if(y == 9) return find(x+1, 0);
	else {
		if(s[x][y] != 0) return find(x, y+1);
		for(i = 1; i <= 9; i++) {
			if(!set(x, y, i, true)) continue;
			s[x][y] = i;
			if(find(x, y+1)) return true;
			set(x, y, i, false); s[x][y] = 0;
		}
		return false;
	}
}