社区讨论
还没写完 dfs 就错了求条
P4573[CQOI2013] 新数独参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mjm8l98i
- 此快照首次捕获于
- 2025/12/26 10:12 2 个月前
- 此快照最后确认于
- 2025/12/27 21:05 2 个月前
代码稍微长了一点。
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
int n=9,t;
char a[N][N],aa[N][N];
map<pair<int,int>,map<pair<int,int>,bool>> mp;
bool b[N][N],c[N][N],d[N][N],is;
int dx[]={1,-1,0,0,1,1,-1,-1};
int dy[]={0,0,1,-1,1,-1,1,-1};
void Clear(){
is=0;
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
b[i][j]=0;
c[i][j]=0;
d[i][j]=0;
}
}
}
int yal(){
for(int i=1;i<=2;i++){
if(mp[{1,i}][{1,i+1}]==1){
if(a[1][i]<a[1][i+1]){
return 0;
}
}
else{
if(a[1][i]>a[1][i+1]){
return 0;
}
}
}
for(int i=4;i<=5;i++){
if(mp[{1,i}][{1,i+1}]==1){
if(a[1][i]<a[1][i+1]){
return 0;
}
}
else{
if(a[1][i]>a[1][i+1]){
return 0;
}
}
}
for(int i=7;i<=8;i++){
if(mp[{1,i}][{1,i+1}]==1){
if(a[1][i]<a[1][i+1]){
return 0;
}
}
else{
if(a[1][i]>a[1][i+1]){
return 0;
}
}
}
// BBB
for(int i=1;i<=9;i++){
if(mp[{1,i}][{2,i}]==1){
if(a[1][i]<a[2][i]){
return 0;
}
}
else{
if(a[1][i]>a[2][i]){
return 0;
}
}
}
// 记得继续
return 1;
}
int xzk(){
for(int i=1;i<=n;i++){
unordered_set<char> s;
for(int j=1;j<=n;j++){
s.insert(a[i][j]);
}
if(s.size()!=n){
return 0;
}
}
for(int i=1;i<=n;i++){
unordered_set<char> s;
for(int j=1;j<=n;j++){
s.insert(a[j][i]);
}
if(s.size()!=n){
return 0;
}
}
for(int i=2;i<=n;i+=3){
for(int j=2;j<=n;j+=3){
unordered_set<char> s;
for(int k=0;k<8;k++){
int sx=i+dx[k],sy=j+dy[k];
s.insert(a[sx][sy]);
}
s.insert(a[i][j]);
if(s.size()!=n){
return 0;
}
}
}
if(!yal()){
return 0;
}
return 1;
}
void Print(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<a[i][j]<<" ";
}
cout<<"\n";
}
}
void dfs(int x,int y){
if(is==1){
return;
}
if(x==9&&y>9){
if(xzk()){
Print();
is=1;
}
return;
}
else if(x==9){
if(y>9){
dfs(x,10);
return;
}
if(a[x][y]!='.'){
dfs(x,y+1);
return;
}
for(int i=1;i<=n;i++){
int tt=((x-1)/3)*3+((y-1)/3)+1;
if(b[x][i]==0&&c[y][i]==0&&d[tt][i]==0){
b[x][i]=1;
c[y][i]=1;
d[tt][i]=1;
a[x][y]=char(i+'0');
dfs(x,y+1);
b[x][i]=0;
c[y][i]=0;
d[tt][i]=0;
a[x][y]='.';
}
}
return;
}
else if(y>9){
dfs(x+1,1);
return;
}
else if(y==9){
if(a[x][y]!='.'){
dfs(x,y+1);
return;
}
for(int i=1;i<=n;i++){
int tt=((x-1)/3)*3+((y-1)/3)+1;
if(b[x][i]==0&&c[y][i]==0&&d[tt][i]==0){
b[x][i]=1;
c[y][i]=1;
d[tt][i]=1;
a[x][y]=char(i+'0');
dfs(x,y+1);
b[x][i]=0;
c[y][i]=0;
d[tt][i]=0;
a[x][y]='.';
}
}
return;
}
else if(a[x][y]!='.'){
dfs(x,y+1);
return;
}
else{
for(int i=1;i<=n;i++){
int tt=((x-1)/3)*3+((y-1)/3)+1;
if(b[x][i]==0&&c[y][i]==0&&d[tt][i]==0){
if(x==1&&y==2){
if(mp[{1,1}][{1,2}]==1){
if(i+'0'>a[1][1]){
continue;
}
}
else{
if(i+'0'<a[1][1]){
continue;
}
}
}
if(x==1&&y==3){
if(mp[{1,2}][{1,3}]==1){
if(i+'0'>a[1][2]){
continue;
}
}
else{
if(i+'0'<a[1][2]){
continue;
}
}
}
if(x==1&&y==5){
if(mp[{1,4}][{1,5}]==1){
if(i+'0'>a[1][4]){
continue;
}
}
else{
if(i+'0'<a[1][4]){
continue;
}
}
}
if(x==1&&y==6){
if(mp[{1,5}][{1,6}]==1){
if(i+'0'>a[1][5]){
continue;
}
}
else{
if(i+'0'<a[1][5]){
continue;
}
}
}
if(x==1&&y==8){
if(mp[{1,7}][{1,8}]==1){
if(i+'0'>a[1][7]){
continue;
}
}
else{
if(i+'0'<a[1][7]){
continue;
}
}
}
if(x==2&&y==1){
if(mp[{1,1}][{2,1}]==1){
if(i+'0'>a[1][1]){
continue;
}
}
else{
if(i+'0'<a[1][1]){
continue;
}
}
}
if(x==2&&y==2){
if(mp[{1,2}][{2,2}]==1){
if(i+'0'>a[1][2]){
continue;
}
}
else{
if(i+'0'<a[1][2]){
continue;
}
}
if(mp[{2,1}][{2,2}]==1){
if(i+'0'>a[2][1]){
continue;
}
}
else{
if(i+'0'<a[2][1]){
continue;
}
}
}
if(x==2&&y==3){
if(mp[{1,3}][{2,3}]==1){
if(i+'0'>a[1][3]){
continue;
}
}
else{
if(i+'0'<a[1][3]){
continue;
}
}
if(mp[{2,2}][{2,3}]==1){
if(i+'0'>a[2][2]){
continue;
}
}
else{
if(i+'0'<a[2][2]){
continue;
}
}
}
if(x==2&&y==5){
if(mp[{1,5}][{2,5}]==1){
if(i+'0'>a[1][5]){
continue;
}
}
else{
if(i+'0'<a[1][5]){
continue;
}
}
if(mp[{2,4}][{2,5}]==1){
if(i+'0'>a[2][4]){
continue;
}
}
else{
if(i+'0'<a[2][4]){
continue;
}
}
}
if(x==2&&y==6){
if(mp[{1,6}][{2,6}]==1){
if(i+'0'>a[1][6]){
continue;
}
}
else{
if(i+'0'<a[1][6]){
continue;
}
}
if(mp[{2,5}][{2,6}]==1){
if(i+'0'>a[2][5]){
continue;
}
}
else{
if(i+'0'<a[2][5]){
continue;
}
}
}
if(x==2&&y==8){
if(mp[{1,8}][{2,8}]==1){
if(i+'0'>a[1][8]){
continue;
}
}
else{
if(i+'0'<a[1][8]){
continue;
}
}
if(mp[{2,7}][{2,8}]==1){
if(i+'0'>a[2][7]){
continue;
}
}
else{
if(i+'0'<a[2][7]){
continue;
}
}
}
// 3
if(x==3&&y==1){
if(mp[{2,1}][{3,1}]==1){
if(i+'0'>a[2][1]){
continue;
}
}
else{
if(i+'0'<a[2][1]){
continue;
}
}
}
if(x==3&&y==2){
if(mp[{2,2}][{3,2}]==1){
if(i+'0'>a[2][2]){
continue;
}
}
else{
if(i+'0'<a[2][2]){
continue;
}
}
if(mp[{3,1}][{3,2}]==1){
if(i+'0'>a[3][1]){
continue;
}
}
else{
if(i+'0'<a[3][1]){
continue;
}
}
}
if(x==3&&y==3){
if(mp[{2,3}][{3,3}]==1){
if(i+'0'>a[2][3]){
continue;
}
}
else{
if(i+'0'<a[2][3]){
continue;
}
}
if(mp[{3,2}][{3,3}]==1){
if(i+'0'>a[3][2]){
continue;
}
}
else{
if(i+'0'<a[3][2]){
continue;
}
}
}
if(x==3&&y==4){
if(mp[{2,4}][{3,4}]==1){
if(i+'0'>a[2][4]){
continue;
}
}
else{
if(i+'0'<a[2][4]){
continue;
}
}
}
if(x==3&&y==5){
if(mp[{2,5}][{3,5}]==1){
if(i+'0'>a[2][5]){
continue;
}
}
else{
if(i+'0'<a[2][5]){
continue;
}
}
if(mp[{3,4}][{3,5}]==1){
if(i+'0'>a[3][4]){
continue;
}
}
else{
if(i+'0'<a[3][4]){
continue;
}
}
}
if(x==3&&y==6){
if(mp[{2,6}][{3,6}]==1){
if(i+'0'>a[2][6]){
continue;
}
}
else{
if(i+'0'<a[2][6]){
continue;
}
}
if(mp[{3,5}][{3,6}]==1){
if(i+'0'>a[3][5]){
continue;
}
}
else{
if(i+'0'<a[3][5]){
continue;
}
}
}
if(x==3&&y==7){
if(mp[{2,7}][{3,7}]==1){
if(i+'0'>a[2][7]){
continue;
}
}
else{
if(i+'0'<a[2][7]){
continue;
}
}
}
if(x==3&&y==8){
if(mp[{2,8}][{3,8}]==1){
if(i+'0'>a[2][8]){
continue;
}
}
else{
if(i+'0'<a[2][8]){
continue;
}
}
if(mp[{3,7}][{3,8}]==1){
if(i+'0'>a[3][7]){
continue;
}
}
else{
if(i+'0'<a[3][7]){
continue;
}
}
}
if(x==3&&y==9){
if(mp[{2,9}][{3,9}]==1){
if(i+'0'>a[2][9]){
continue;
}
}
else{
if(i+'0'<a[2][9]){
continue;
}
}
if(mp[{3,8}][{3,9}]==1){
if(i+'0'>a[3][8]){
continue;
}
}
else{
if(i+'0'<a[3][8]){
continue;
}
}
}
// 记得继续
b[x][i]=1;
c[y][i]=1;
d[tt][i]=1;
a[x][y]=char(i+'0');
dfs(x,y+1);
b[x][i]=0;
c[y][i]=0;
d[tt][i]=0;
a[x][y]='.';
}
}
}
}
signed main(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]='.';
}
}
char aa;
// 1==========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{1,j}][{1,j+1}]=1;
mp[{1,j+1}][{1,j}]=-1;
}
else{
mp[{1,j}][{1,j+1}]=-1;
mp[{1,j+1}][{1,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{1,j}][{1,j+1}]=1;
mp[{1,j+1}][{1,j}]=-1;
}
else{
mp[{1,j}][{1,j+1}]=-1;
mp[{1,j+1}][{1,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{1,j}][{1,j+1}]=1;
mp[{1,j+1}][{1,j}]=-1;
}
else{
mp[{1,j}][{1,j+1}]=-1;
mp[{1,j+1}][{1,j}]=1;
}
}
// 2=========================
for(int i=1;i<=9;i++){
cin>>aa;
if(aa=='v'){
mp[{1,i}][{2,i}]=1;
mp[{2,i}][{1,i}]=-1;
}
else{
mp[{1,i}][{2,i}]=-1;
mp[{2,i}][{1,i}]=1;
}
}
// 3========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{2,j}][{2,j+1}]=1;
mp[{2,j+1}][{2,j}]=-1;
}
else{
mp[{2,j}][{2,j+1}]=-1;
mp[{2,j+1}][{2,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{2,j}][{2,j+1}]=1;
mp[{2,j+1}][{2,j}]=-1;
}
else{
mp[{2,j}][{2,j+1}]=-1;
mp[{2,j+1}][{2,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{2,j}][{2,j+1}]=1;
mp[{2,j+1}][{2,j}]=-1;
}
else{
mp[{2,j}][{2,j+1}]=-1;
mp[{2,j+1}][{2,j}]=1;
}
}
// 4============================
for(int i=1;i<=9;i++){
cin>>aa;
if(aa=='v'){
mp[{2,i}][{3,i}]=1;
mp[{3,i}][{2,i}]=-1;
}
else{
mp[{2,i}][{3,i}]=-1;
mp[{3,i}][{2,i}]=1;
}
}
// 5===========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{3,j}][{3,j+1}]=1;
mp[{3,j+1}][{3,j}]=-1;
}
else{
mp[{3,j}][{3,j+1}]=-1;
mp[{3,j+1}][{3,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{3,j}][{3,j+1}]=1;
mp[{3,j+1}][{3,j}]=-1;
}
else{
mp[{3,j}][{3,j+1}]=-1;
mp[{3,j+1}][{3,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{3,j}][{3,j+1}]=1;
mp[{3,j+1}][{3,j}]=-1;
}
else{
mp[{3,j}][{3,j+1}]=-1;
mp[{3,j+1}][{3,j}]=1;
}
}
// =+-=+-=+-=+-=+-=+-=+-
// 1==========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{4,j}][{4,j+1}]=1;
mp[{4,j+1}][{4,j}]=-1;
}
else{
mp[{4,j}][{4,j+1}]=-1;
mp[{4,j+1}][{4,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{4,j}][{4,j+1}]=1;
mp[{4,j+1}][{4,j}]=-1;
}
else{
mp[{4,j}][{4,j+1}]=-1;
mp[{4,j+1}][{4,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{4,j}][{4,j+1}]=1;
mp[{4,j+1}][{4,j}]=-1;
}
else{
mp[{4,j}][{4,j+1}]=-1;
mp[{4,j+1}][{4,j}]=1;
}
}
// 2=========================
for(int i=1;i<=9;i++){
cin>>aa;
if(aa=='v'){
mp[{4,i}][{5,i}]=1;
mp[{5,i}][{4,i}]=-1;
}
else{
mp[{4,i}][{5,i}]=-1;
mp[{5,i}][{4,i}]=1;
}
}
// 3========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{5,j}][{5,j+1}]=1;
mp[{5,j+1}][{5,j}]=-1;
}
else{
mp[{5,j}][{5,j+1}]=-1;
mp[{5,j+1}][{5,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{5,j}][{5,j+1}]=1;
mp[{5,j+1}][{5,j}]=-1;
}
else{
mp[{5,j}][{5,j+1}]=-1;
mp[{5,j+1}][{5,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{5,j}][{5,j+1}]=1;
mp[{5,j+1}][{5,j}]=-1;
}
else{
mp[{5,j}][{5,j+1}]=-1;
mp[{5,j+1}][{5,j}]=1;
}
}
// 4============================
for(int i=1;i<=9;i++){
cin>>aa;
if(aa=='v'){
mp[{5,i}][{6,i}]=1;
mp[{6,i}][{5,i}]=-1;
}
else{
mp[{5,i}][{6,i}]=-1;
mp[{6,i}][{5,i}]=1;
}
}
// 5===========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{6,j}][{6,j+1}]=1;
mp[{6,j+1}][{6,j}]=-1;
}
else{
mp[{6,j}][{6,j+1}]=-1;
mp[{6,j+1}][{6,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{6,j}][{6,j+1}]=1;
mp[{6,j+1}][{6,j}]=-1;
}
else{
mp[{6,j}][{6,j+1}]=-1;
mp[{6,j+1}][{6,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{6,j}][{6,j+1}]=1;
mp[{6,j+1}][{6,j}]=-1;
}
else{
mp[{6,j}][{6,j+1}]=-1;
mp[{6,j+1}][{6,j}]=1;
}
}
// =+-=+-=+-=+-=+-=+-=+-
// 1==========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{7,j}][{7,j+1}]=1;
mp[{7,j+1}][{7,j}]=-1;
}
else{
mp[{7,j}][{7,j+1}]=-1;
mp[{7,j+1}][{7,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{7,j}][{7,j+1}]=1;
mp[{7,j+1}][{7,j}]=-1;
}
else{
mp[{7,j}][{7,j+1}]=-1;
mp[{7,j+1}][{7,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{7,j}][{7,j+1}]=1;
mp[{7,j+1}][{7,j}]=-1;
}
else{
mp[{7,j}][{7,j+1}]=-1;
mp[{7,j+1}][{7,j}]=1;
}
}
// 2=========================
for(int i=1;i<=9;i++){
cin>>aa;
if(aa=='v'){
mp[{7,i}][{8,i}]=1;
mp[{8,i}][{7,i}]=-1;
}
else{
mp[{7,i}][{8,i}]=-1;
mp[{8,i}][{7,i}]=1;
}
}
// 3========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{8,j}][{8,j+1}]=1;
mp[{8,j+1}][{8,j}]=-1;
}
else{
mp[{8,j}][{8,j+1}]=-1;
mp[{8,j+1}][{8,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{8,j}][{8,j+1}]=1;
mp[{8,j+1}][{8,j}]=-1;
}
else{
mp[{8,j}][{8,j+1}]=-1;
mp[{8,j+1}][{8,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{8,j}][{8,j+1}]=1;
mp[{8,j+1}][{8,j}]=-1;
}
else{
mp[{8,j}][{8,j+1}]=-1;
mp[{8,j+1}][{8,j}]=1;
}
}
// 4============================
for(int i=1;i<=9;i++){
cin>>aa;
if(aa=='v'){
mp[{8,i}][{9,i}]=1;
mp[{9,i}][{8,i}]=-1;
}
else{
mp[{8,i}][{9,i}]=-1;
mp[{9,i}][{8,i}]=1;
}
}
// 5===========================
for(int j=1;j<=2;j++){
cin>>aa;
if(aa=='>'){
mp[{9,j}][{9,j+1}]=1;
mp[{9,j+1}][{9,j}]=-1;
}
else{
mp[{9,j}][{9,j+1}]=-1;
mp[{9,j+1}][{9,j}]=1;
}
}
for(int j=4;j<=5;j++){
cin>>aa;
if(aa=='>'){
mp[{9,j}][{9,j+1}]=1;
mp[{9,j+1}][{9,j}]=-1;
}
else{
mp[{9,j}][{9,j+1}]=-1;
mp[{9,j+1}][{9,j}]=1;
}
}
for(int j=7;j<=8;j++){
cin>>aa;
if(aa=='>'){
mp[{9,j}][{9,j+1}]=1;
mp[{9,j+1}][{9,j}]=-1;
}
else{
mp[{9,j}][{9,j+1}]=-1;
mp[{9,j+1}][{9,j}]=1;
}
}
dfs(1,1);
return 0;
}
回复
共 0 条回复，欢迎继续交流。
正在加载回复...