《一 开 O 2 见 祖 宗》蒟蒻第一次写厌氧代码,求助!
  • 板块P1784 数独
  • 楼主doris_xyb
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/7/4 13:17
  • 上次更新2023/11/3 11:39:55
查看原帖
《一 开 O 2 见 祖 宗》蒟蒻第一次写厌氧代码,求助!
731828
doris_xyb楼主2023/7/4 13:17

蒟蒻只希望懂得,为啥开O2会 WA \textcolor{red}{WA}\ ?

#include <iostream>
#include <algorithm>
using namespace std;
int yx[10],ixy,a[10][10];
bool h[10][10],l[10][10],g[10][10],flag;
struct node{
	int cnt,id;
}c[10];
bool cnt(node a,node b){
	return a.cnt<b.cnt;
}
struct m{
	int x,y;
}w[10];
bool cnt2(m a,m b){
	if(a.x!=b.x) return yx[a.x]<yx[b.x];
	else return a.y<b.y;
}
void dfs(int id){
	if(flag){
		return ;
	}
	if(id==ixy+1){
		for(int i = 1;i <= 9;i++){
			for(int j = 1;j <= 9;j++){
				cout << a[i][j] << " ";
			}
			cout << endl;
		}
		flag=1;
		return ;
	}
	for(int i = 1;i <= 9;i++){
		if(!h[w[id].x][i] && !l[w[id].y][i] && !g[(w[id].x-1)/3*3+(w[id].y-1)/3+1][i]){
			h[w[id].x][i]=1;
			l[w[id].y][i]=1;
			g[(w[id].x-1)/3*3+(w[id].y-1)/3+1][i]=1;
			a[w[id].x][w[id].y]=i;
			dfs(id+1);
			h[w[id].x][i]=0;
			l[w[id].y][i]=0;
			g[(w[id].x-1)/3*3+(w[id].y-1)/3+1][i]=0;
		}
	}
}
int main(){
	for(int i = 1;i <= 9;i++){
		c[i].id=i;
		for(int j = 1;j <= 9;j++){
			cin >> a[i][j];
			if(!a[i][j]){
				c[i].cnt++;
				w[++ixy].x=i;
				w[ixy].y=j;
			}
			else{
				h[i][a[i][j]]=1;
				l[j][a[i][j]]=1;
				g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
			}
		}
	}
	sort(c+1,c+10,cnt);
	for(int i = 1;i <= 9;i++){
		yx[c[i].id]=i;
	}
	sort(w+1,w+10,cnt2);
	dfs(1);
	return 0;
}
2023/7/4 13:17
加载中...