80pts,#4TLE
  • 板块P1784 数独
  • 楼主mediocre_
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/9/6 21:17
  • 上次更新2023/10/27 12:23:04
查看原帖
80pts,#4TLE
565707
mediocre_楼主2022/9/6 21:17
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int a[N][N];
int hang[N][N], lie[N][N], gong[N][N];
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
void dfs(register int x, register int y) {
	//printf("--------------------\n");
	//for (int i = 1; i <= 9; ++i) {
	//	for (int j = 1; j <= 9; ++j)
	//		printf("%d ", a[i][j]);
	//	printf("\n");
	//}
	if (a[x][y] != 0) {
		if (x == 9 && y == 9) {
			for (register int i = 1; i <= 9; ++i) {
				for (register int j = 1; j <= 9; ++j) {
					write(a[i][j]);
					putchar(' ');
				}
				putchar('\n');
			}
			return;
		} else if (y == 9)dfs(x + 1, 1);
		else dfs(x, y + 1);
	} else {
		for (register int i = 1; i <= 9; ++i)
			if (hang[x][i] == 0 && lie[y][i] == 0 && gong[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][i] == 0) {
				a[x][y] = i;
				hang[x][i] = 1;
				lie[y][i] = 1;
				gong[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][i] = 1;
				if (x == 9 && y == 9) {
					for (register int i = 1; i <= 9; ++i) {
						for (register int j = 1; j <= 9; ++j) {
							write(a[i][j]);
							putchar(' ');
						}
						putchar('\n');
					}
					return;
				} else if (y == 9)dfs(x + 1, 1);
				else dfs(x, y + 1);
				hang[x][i] = 0;
				lie[y][i] = 0;
				gong[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][i] = 0;
				a[x][y] = 0;
			}
	}
}
int main() {
	for (register int i = 1; i <= 9; ++i)
		for (register int j = 1; j <= 9; ++j) {
			hang[i][j] = 0;
			lie[i][j] = 0;
			gong[i][j] = 0;
		}
	for (register int i = 1; i <= 9; ++i)
		for (register int j = 1; j <= 9; ++j) {
			register int x;
			x = read();
			a[i][j] = x;
			if (x != 0) {
				hang[i][x] = 1;
				lie[j][x] = 1;
				gong[(i - 1) / 3 * 3 + (j - 1) / 3 + 1][x] = 1;
			}
		}
	dfs(1, 1);
	/*for (int i = 1; i <= 9; ++i) {
		for (int j = 1; j <= 9; ++j)
			printf("%d ", a[i][j]);
		printf("\n");
	}*/
	return 0;
}
2022/9/6 21:17
加载中...