全RE求调
  • 板块P1784 数独
  • 楼主goodier
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/8/6 09:34
  • 上次更新2023/10/27 16:48:03
查看原帖
全RE求调
242039
goodier楼主2022/8/6 09:34

rt,输出正常,主函数return 0前的代码都正常,就是主函数会返回一个3开头的值,求大佬帮调

#include <bits/stdc++.h>
using namespace std;
int ones[1 << 9],Map[1 << 9],hang[12],lie[12],jgg[4][4],all = (1 << 9) - 1;
string a;
inline int lowbit(int x)
{
	return x & -x;
}

inline int count(int x)
{
	int cnt = 0;
	while(x)
	{
		x -= lowbit(x);
		cnt++;
	}
	return cnt;
}

inline int get(int x,int y)
{
	return hang[x] & lie[y] & jgg[x / 3][y / 3];
}

bool dfs(int cnt)
{ 
	if(!cnt) return true;
	int posh,posl,ans = 10;
	for(int i = 0; i <= 8; i++)
	{
		for(int j = 0; j <= 8; j++)
		{
			if(a[i * 9 + j] == '0')
			{
				int t = ones[get(i,j)];
				if(t < ans)
				{
					ans = t;
					posh = i;
					posl = j;
				 } 
			}
		}
	}
	for(int i = get(posh,posl); i; i -= lowbit(i))
	{
		int t = Map[lowbit(i)];
		hang[posh] -= 1 << t,lie[posl] -= 1 << t,jgg[posh / 3][posl / 3] -= 1 << t;
		a[posh * 9 + posl] = '1' + t;
		if(dfs(cnt - 1)) return true;
		hang[posh] += 1 << t,lie[posl] += 1 << t,jgg[posh / 3][posl / 3] += 1 << t;
		a[posh * 9 + posl] = '0';
	}
	return false;
}
void init()
{
	for(int i = 0; i <= 8; i++)
	{
		hang[i] = all,lie[i] = all,jgg[i / 3][i % 3] = all;
	}
}
int main()
{
	for(int i = 0; i <= 1 << 9; i++)
	{
		ones[i] = count(i);
	}
	for(int i = 0; i < 9; i++)
	{
		Map[1 << i] = i;
	}
	int cnt = 0;
	init();
	for(int i = 0,k = 0; i <= 8; i++)
	{
		for(int j = 0; j <= 8; j++,k++)
		{
			cin >> a[k];
		    while (a[k] == '\r' ||a[k] == '\n' || a[k] == ' ') cin >> a[k];
			if(a[k] != '0')
			{
				int t = a[k] - '1';
				hang[i] -= 1 << t;
				lie[j] -= 1 << t;
				jgg[i / 3][j / 3] -= 1 << t;
			}
			else ++cnt;
		}
	}
	dfs(cnt);
	for(int i = 0; i <= 8; i++)
	{
	    for(int j = 0; j <= 8; j++)
	    {
	       	printf("%c ",a[i * 9 + j]);
	    }
	    printf("\n");
	}
	return 0;
}
2022/8/6 09:34
加载中...