題目地址 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2764 就是讓你寫(xiě)一個(gè)計(jì)算數(shù)獨(dú)的程序 這個(gè)程序有幾個(gè)條件 1 輸入o處填奇數(shù) 2 輸入e處天偶數(shù) 3 輸入0處隨便填 4 輸入相同小寫(xiě)字符的地方要寫(xiě)相同的數(shù) 5 每一個(gè)3*3的小矩陣?yán)?-9每個(gè)數(shù)都有 每一行每一列1-9都有 計(jì)算一共有多少種符合條件的數(shù)獨(dú)種類(lèi)數(shù)量
解法：暴力搜索 分析每次搜索其實(shí)就是條件哪幾種情況分別處理就行 注意可以把每一個(gè)小矩陣可以按照對(duì)應(yīng)下表去搞一個(gè)標(biāo)記矩陣 bool bok[i][j] 表示 第i個(gè)矩陣是否標(biāo)記過(guò)j 對(duì)于下標(biāo) x y 對(duì)應(yīng)就是第(x/3*3 + y/3 )個(gè)矩陣
還有一個(gè)地方不好處理 就是對(duì)于第4個(gè)條件 這里我們需要在搞一個(gè)aph數(shù)組 記錄某字符下存的數(shù)是多少 第一次遇到通常放 下次遇到相同字符直接拿出來(lái)判斷 可行就放 不可行回溯回去修改原來(lái)的數(shù)
code： //1 數(shù)字非0->跳過(guò) //2 0 進(jìn)入模式搜索 //3 o 進(jìn)入奇數(shù)搜索 //4 e 進(jìn)入偶數(shù)搜索 //5 其他alp字符 找之前記錄的數(shù)字 如果沒(méi)有重新搜索一個(gè)新數(shù)字 #include<bits/stdc++.h> using namespace std; char p[12][12]; int ans[12][12],c;// 結(jié)果矩陣 bool bok[12][10];//9 個(gè)正方形 每個(gè)里面有1-9 int aph[30]; void dfs(int x,int y); void next(int x,int y) {if(y<8&&x<=8)dfs(x,y+1);else if(y==8&&x<8)dfs(x+1,0);else if(y==8&&x==8){c++;return;} } bool check(int x,int y,int n) {for(int i=0;i<9;i++)if(ans[x][i]==n)return 0;for(int i=0;i<9;i++)if(ans[i][y]==n)return 0;return 1; } void dfs(int x,int y) { int d = x/3*3+y/3;if(p[x][y]=='0'){for(int i=1;i<10;i++){if(check(x,y,i)&&!bok[d][i]){// 檢查同行同列 和矩陣標(biāo)記信息bok[d][i]=1;ans[x][y]=i;next(x,y);bok[d][i]=0;ans[x][y]=0;}}}else if(p[x][y]=='e'){for(int i=2;i<10;i+=2){if(check(x,y,i)&&!bok[d][i]){bok[d][i]=1;ans[x][y]=i;next(x,y);bok[d][i]=0;ans[x][y]=0;}}}else if(p[x][y]=='o'){for(int i=1;i<10;i+=2){if(check(x,y,i)&&!bok[d][i]){bok[d][i]=1;ans[x][y]=i;next(x,y);bok[d][i]=0;ans[x][y]=0;}}}else if(islower(p[x][y])){int t = p[x][y]-'a';if(aph[t]==0){// 如果沒(méi)放過(guò)for(int i=1;i<10;i++)if(!bok[d][i]&&check(x,y,i)){bok[d][i]=1;ans[x][y] = i;aph[t]=i;next(x,y);aph[t]=0;bok[d][i]=0;ans[x][y] = 0;} }else {//放過(guò)if(!bok[d][aph[t]]&&check(x,y,aph[t])){//可行ans[x][y]=aph[t];bok[d][aph[t]]=1;next(x,y);bok[d][aph[t]]=0;ans[x][y] = 0; } else return;//不可行}}else next(x,y); } int main() {int t;cin>>t;getchar();while(t--){ c=0;memset(bok,0,sizeof(bok));memset(ans,0,sizeof(ans));memset(aph,0,sizeof(aph));for(int i=0;i<9;i++){for(int j=0;j<9;j++){scanf("%c",&p[i][j]); int d = i/3*3+j/3;if(p[i][j]!='0'&&isdigit(p[i][j])){ans[i][j]=p[i][j]-'0';bok[d][p[i][j]-'0']=1;}} getchar();} dfs(0,0);cout<<c<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Sudoku Extension UVALive - 4763的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。