为什么找不到合法方案啊?
查看原帖
为什么找不到合法方案啊?
565450
__K2FeO4楼主2022/5/22 12:14

最后的注释加上就会被打印出来。

#include<bits/stdc++.h>
using namespace std;
int a[11][11]={0};
bool raw[11][11]={0},cal[11][11]={0},blo[5][5][11]={0};
char xx[11][11]={0},yy[11][11]={0};
void print(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++)
		printf("%d ",a[i][j]);
		puts("");
	}
}
bool sign(char c){
	if(c=='<'||c=='^')return true;
	return false;
}
void dfs(int x,int y){
	if(x==10&&y==1)print(),exit(0);
	int nx,ny;
	if(y==9)nx=x+1,ny=1;
	else nx=x,ny=y+1;
	int l=0,r=10;
	
	if(y%3!=1){
		if(yy[x][y]=='<')l=max(l,a[x][y-1]);
		else r=min(r,a[x][y-1]);
	}
	//else cout<<"pass"<<endl;
	
	if(x%3!=1){
		if(xx[x][y]=='^')l=max(l,a[x-1][y]);
		else r=min(r,a[x-1][y]);
	}
	//else cout<<"pass"<<endl;
	//cout<<l<<' '<<r<<endl;
	
	if(l+1<r)for(int i=l+1;i<r;i++){
		if(raw[x][i]||cal[y][i]||blo[(x-1)/3][(y-1)/3][i])continue;
		a[x][y]=i;raw[x][i]=cal[y][i]=blo[(x-1)/3][(y-1)/3][i]=true;
		//printf("%d\ndfs(%d,%d),",a[x][y],nx,ny);
		dfs(nx,ny);
		a[x][y]=0;raw[x][i]=cal[y][i]=blo[(x-1)/3][(y-1)/3][i]=false;
	}
	//printf("return\n");
}
int main(){
	
	memset(xx,32,sizeof(xx));
	memset(yy,32,sizeof(yy));
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) { 
			if (j % 3 == 1) continue;
			char ch=0;
			while(ch != '<' && ch != '>' && ch != '^' && ch != 'v') ch = getchar();
			yy[i][j]=ch;
			//cout<<yy[i][j]<<' ';
		}
		//cout<<endl;
		
		for (int j = 1; j <= 9; j++) { 
			if (i % 3 == 1) continue;
			char ch=0;
			while(ch != '<' && ch != '>' && ch != '^' && ch != 'v') ch = getchar();
			xx[i][j]=ch;
			//cout<<xx[i][j]<<' ';
		}
		//cout<<endl;
	}
	//cout<<"start dfs(1,1)"<<endl;
    dfs(1,1);
    //cout<<"Fail"<<endl;
	return 0;
}
2022/5/22 12:14
加载中...