求调,80分 最后一个TLE,谢谢
  • 板块P1784 数独
  • 楼主niveKmAI
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/6/10 11:46
  • 上次更新2023/10/23 13:31:04
查看原帖
求调,80分 最后一个TLE,谢谢
867875
niveKmAI楼主2023/6/10 11:46
#include<bits/stdc++.h>
using namespace std;
const int n=9;
char a[n][n];
int sum=0;
bool su(int x,int y,char b){
  for(int i=0; i<n; i++){
    if(a[x][i]==b){
      return false;
      break;
    }
  }
  for(int i=0; i<n; i++){
    if(a[i][y]==b){
      return false;
      break;
    }
  }
  int start_x1=(x/3)*3;
  int start_y1=(y/3)*3;
  for(int i= start_x1; i< start_x1+3; i++){
    for(int j=start_y1; j< start_y1+3; j++){
      if(a[i][j]==b){
        return false;
        break;
      }
    }
  }
  return true;
}
bool dfs(int x,int y ){
  if(x==n){
    return true;
    }
  if(y==n){
    return dfs(x+1,0);
  }
  if(a[x][y]!='0'){
    return dfs(x,y+1);
  }
      for(char c='1'; c<='9'; c++){
      if(su(x,y,c)==true){
        a[x][y]=c;
         if(dfs(x,y+1)==true){  
           return true;  
           break;
          }
       a[x][y]='0';
        continue;
       } 
     }     
  return false;
}
int main(){
	for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
    cin>>a[i][j];
    }
  }
if(dfs(0,0)==true){
  	for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        cout<<a[i][j]<<" ";
    }
      cout<<endl;
  }
}
  
	return 0;
 }
2023/6/10 11:46
加载中...