为什么4x4阶矩阵可用,9x9矩阵结果都输出不出来?求大佬看看
  • 板块P1784 数独
  • 楼主Dreamerlee✅
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/12/31 16:51
  • 上次更新2023/10/28 13:18:48
查看原帖
为什么4x4阶矩阵可用,9x9矩阵结果都输出不出来?求大佬看看
463562
Dreamerlee✅楼主2021/12/31 16:51
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100], row, col, block, b1[11][10], b2[11][10], b3[11][10];
void print()
{
	for (int i = 1; i <= 81; i++)
	{
    //使用一维数组输出
		cout << a[i] << " ";
		if (i % 9 == 0)//换行
			cout << endl;
	}
	exit(0);//退出
}
void dfs(int x,int row,int col)
{
//加个int row,int col是为方便了回溯
//虽然下面会改变row,col但是不影响回溯
	if (a[x] != 0)//如果这个数不是0,代表已经填充过,直接找下一个数
		dfs(x + 1,row,col);
	if (x > 81)//如果81个数全部填完就输出
	{
		print();
	}
	row = (x - 1) / 9 + 1;//所属的行
	col = (x - 1) % 9 + 1;//所属的列
	block = (row - 1) / 3 * 3 + (col - 1) / 3 + 1;//所属的小块
	for (int i = 1; i <= 9; i++)
	{
		//如果该行、列、所在的9*9矩形中,这个数没有填过,就填这个数
		if (b1[row][i] == 0 && b2[col][i] == 0 && b3[block][i] == 0)
		{
			a[x] = i;//填数
			b1[row][i] = 1; b2[col][i] = 1; b3[block][i] = 1;//占位
			if (x > 81)//如果81个数全部填完就输出
			{
				print();
			}
			dfs(x + 1,row,col);//找下一个数
			b1[row][i] = 0; b2[col][i] = 0; b3[block][i] = 0;//取消占位
			a[x] = 0;//取消填数
		}
	}
	return;
}
int main()
{
	for (int i = 1; i <= 81; i++)
	{
		int t;
		cin >> t;
		if (t!= 0)
		{
			a[i] = t;
			row = (i - 1) / 9 + 1;//行
			col = (i - 1) % 9 + 1;//列
			block = (row - 1) / 3 * 3 + (col - 1) / 3 + 1;//属于哪个小块
			b1[row][t] = 1, b2[col][t] = 1, b3[block][t] = 1;
		}
	}
	dfs(1,1,1);//不带row,col不能有效回溯
 

	return 0;
}
2021/12/31 16:51
加载中...