我們經常使用的數的進制為“常數進制”，即始終逢p進1。例如，p進制數K可表示為
K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n （其中0 <= ai <= p-1），
它可以表示任何一個自然數。
對于這種常數進制表示法，以及各種進制之間的轉換大家應該是很熟悉的了，但大家可能很少聽說變進制數。這里我要介紹一種特殊的變進制數，它能夠被用來實現全排列的Hash函數，并且該Hash函數能夠實現完美的防碰撞和空間利用（不會發生碰撞，且所有空間被完全使用，不多不少）。這種全排列Hash函數也被稱為全排列數化技術。下面，我們就來看看這種變進制數。
我們考查這樣一種變進制數：第1位逢2進1，第2位逢3進1，……，第n位逢n+1進1。它的表示形式為
K = a1*1! + a2*2! + a3*3! + ... + an*n! （其中0 <= ai <= i），
也可以擴展為如下形式（因為按定義a0始終為0），以與p進制表示相對應：
K = a0*0! + a1*1! + a2*2! + a3*3! + ... + an*n! （其中0 <= ai <= i）。
（后面的變進制數均指這種變進制數，且采用前一種表示法）
先讓我們來考查一下該變進制數的進位是否正確。假設變進制數K的第i位ai為i+1，需要進位，而ai*i!=(i+1)*i!=1*(i+1)!，即正確的向高位進1。這說明該變進制數能夠正確進位，從而是一種合法的計數方式。
接下來我們考查n位變進制數K的性質：
（1）當所有位ai均為i時，此時K有最大值
MAX[K] = 1*1! + 2*2! + 3*3! + ... + n*n!
= 1! + 1*1! + 2*2! + 3*3! + ... + n*n! - 1
= (1+1)*1! + 2*2! + 3*3! + ... + n*n! - 1
= 2! + 2*2! + 3*3! + ... + n*n! - 1
= ...
= (n+1)!-1
因此，n位K進制數的最大值為(n+1)!-1。
（2）當所有位ai均為0時，此時K有最小值0。
因此，n位變進制數能夠表示0到(n+1)!-1的范圍內的所有自然數，共(n+1)!個。
在一些狀態空間搜索算法中，我們需要快速判斷某個狀態是否已經出現，此時常常使用Hash函數來實現。其中，有一類特殊的狀態空間，它們是由全排列產生的，比如N數碼問題。對于n個元素的全排列，共產生n!個不同的排列或狀態。下面將討論如何使用這里的變進制數來實現一個針對全排列的Hash函數。
從數的角度來看，全排列和變進制數都用到了階乘。如果我們能夠用0到n!-1這n!個連續的變進制數來表示n個元素的所有排列，那么就能夠把全排列完全地數化，建立起全排列和自然數之間一一對應的關系，也就實現了一個完美的Hash函數。那么，我們的想法能否實現呢？答案是肯定的，下面將進行討論。
假設我們有b0,b1,b2,b3,...,bn共n+1個不同的元素，并假設各元素之間有一種次序關系 b0<b1<b2<...<bn。對它們進行全排列，共產生(n+1)!種不同的排列。對于產生的任一排列 c0,c1,c2,..,cn，其中第i個元素ci（1 <= i <= n）與它前面的i個元素構成的逆序對的個數為di（0 <= di <= i），那么我們得到一個逆序數序列d1,d2,...,dn（0 <= di <= i）。這不就是前面的n位變進制數的各個位么？于是，我們用n位變進制數M來表示該排列：
M = d1*1! + d2*2! + ... + dn*n!
因此，每個排列都可以按這種方式表示成一個n位變進制數。下面，我們來考查n位變進制數能否與n+1個元素的全排列建立起一一對應的關系。
由于n位變進制數能表示(n+1)!個不同的數，而n+1個元素的全排列剛好有(n+1)!個不同的排列，且每一個排列都已經能表示成一個n位變進制數。如果我們能夠證明任意兩個不同的排列產生兩個不同的變進制數，那么我們就可以得出結論：
★ 定理1 n+1個元素的全排列的每一個排列對應著一個不同的n位變進制數。
對于全排列的任意兩個不同的排列p0,p1,p2,...,pn（排列P）和q0,q1,q2,...,qn（排列Q），從后往前查找第一個不相同的元素，分別記為pi和qi（0 < i <= n）。
（1）如果qi > pi，那么,
如果在排列Q中qi之前的元素x與qi構成逆序對，即有x > qi，則在排列P中pi之前也有相同元素x > pi（因為x > qi且qi > pi），即在排列P中pi之前的元素x也與pi構成逆序對，所以pi的逆序數大于等于qi的逆序數。又qi與pi在排列P中構成pi的逆序對，所以pi的逆序數大于qi的逆序數。
（2）同理，如果pi > qi，那么qi的逆序數大于pi的逆序數。
因此，由（1）和（2）知，排列P和排列Q對應的變進制數至少有第i位不相同，即全排列的任意兩個不同的排列具有不同的變進制數。至此，定理1得證。
計算n個元素的一個排列的變進制數的算法大致如下（時間復雜度為O(n^2)）：
template <typename T>
size_t PermutationToNumber(const T permutation[], int n)
{
// n不能太大，否則會溢出（如果size_t為32位，則n <= 12）
size_t result = 0;
for (int j = 1; j < n; ++j) {
int count = 0;
for (int k = 0; k < j; ++k) {
if (permutation[k] > permutation[j])
++count;
}
// factorials[j]保存著j!
result += count * factorials[j];
}
return result;
}
說明：
（1）由于n!是一個很大的數，因此一般只能用于較小的n。
（2）有了計算排列的變進制數的算法，我們就可以使用一個大小為n!的數組來保存每一個排列的狀態，使用排列的變進制數作為數組下標，從而實現狀態的快速檢索。如果只是標記狀態是否出現，則可以用一位來標記狀態。
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1775思路:
簡單題，可以打表，可以DFS，還可以動規
代碼(dfs):
1 /* Note: 10! = 3628800 */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 10
6 int facs[MAX_LEN];
7 int mark, n;
8
9 void
10 init()
11 {
12 int i, f = 1;
13 facs[0] = 1;
14 for(i=1; i<MAX_LEN; i++) {
15 facs[i] = f*i;
16 f = facs[i];
17 }
18 }
19
20 void
21 dfs(int depth, int sum)
22 {
23 if(sum == n) {
24 mark = 1;
25 return;
26 }
27 if(depth>=MAX_LEN || mark)
28 return;
29 dfs(depth+1, sum+facs[depth]);
30 dfs(depth+1, sum);
31 }
32
33 int
34 main(int argc, char **argv)
35 {
36 init();
37 while(scanf("%d", &n)!=EOF && n>=0) {
38 mark = 0;
39 if(n > 0)
40 dfs(0, 0);
41 printf("%s\n", mark?"YES":"NO");
42 }
43 }
代碼(table, from
http://blog.chinaunix.net/u3/105033/showart_2199237.html):
1 #include<iostream>
2 using namespace std;
3 bool b[1000001];
4 int sum=0;
5 int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
6 void calculate(int n)
7 {
8 if(n>=10)
9 return ;
10 sum+=a[n];
11 b[sum]=true;
12 calculate(n+1);
13 sum-=a[n];
14 calculate(n+1);
15 }
16 int main()
17 {
18 memset(b,0,sizeof(b[0]));
19 calculate(0);
20 b[0]=false;
21 int n;
22 cin>>n;
23 while( n>=0)
24 {
25 if(b[n])
26 cout<<"YES"<<endl;
27 else
28 cout<<"NO"<<endl;
29 cin>>n;
30 }
31 return 0;
32 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2248思路:
第一個想法是BFS，不過習慣性地看discuss，發現大家用的都是DFS，于是還是用DFS+減枝
這道題目的關鍵減枝是: num[depth+1] = num[depth]+num[i], 0<=i<=depth，另外就是從大到小的搜索順序
另一種解法是迭代加深搜索，第一次使用，貌似就是用DFS實現BFS，不過空間需求與時間需求是兩者的折衷，其模板類似于:
1 for(deep=1; 1; deep++)
2
3 {
4
5 dfs(0);
6
7 If(find = true)
8
9 break;
10
11 }
代碼1:
1 #define MAX_LEN 101
2 #define INF 0x7FFFFFFF
3 int num[MAX_LEN];
4 int ans[MAX_LEN];
5 int n, min;
6
7 int
8 dfs(int depth)
9 {
10 int i, j;
11 if(depth+1 >= min)
12 return;
13 if(num[depth] == n) {
14 min = depth+1;
15 memcpy(ans, num, min*sizeof(int));
16 return;
17 }
18 for(i=depth; i>=0; i--)
19 if(num[i]+num[depth]<=n) {
20 num[depth+1] = num[i] + num[depth];
21 dfs(depth+1);
22 }
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 int i;
29 while(scanf("%d", &n)!=EOF && n!=0) {
30 min = INF;
31 num[0] = 1;
32 dfs(0);
33 for(i=0; i<min; i++)
34 printf("%d ", ans[i]);
35 printf("\n");
36 }
37 return 0;
38 }
代碼2:
1 #define MAX_LEN 101
2 int num[MAX_LEN];
3 int n, find, dplimit;
4
5 void
6 dfs(int depth)
7 {
8 int i, j;
9 if(depth >= dplimit)
10 return;
11 if(num[depth] == n) {
12 if(!find) {
13 for(j=0; j<=depth; j++)
14 printf("%d ", num[j]);
15 printf("\n");
16 find = 1;
17 }
18 return;
19 }
20 for(i=depth; i>=0; i--)
21 if(num[i]+num[depth]<=n) {
22 num[depth+1] = num[i] + num[depth];
23 dfs(depth+1);
24 }
25 }
26
27 int
28 main(int argc, char **argv)
29 {
30 while(scanf("%d", &n)!=EOF && n!=0) {
31 find = 0;
32 num[0] = 1;
33 for(dplimit=1; 1; dplimit++) {
34 dfs(0);
35 if(find)
36 break;
37 }
38 }
39 }
摘要: 問題:http://acm.pku.edu.cn/JudgeOnline/problem?id=1475思路:很復雜的一題，從discuss知道可以采用嵌套的BFS來做，不過始終不知道如何下手通過這題，發現自己對于復雜問題的coding能力比較弱，不能很好的理清其中的邏輯關系，需要多多鍛煉這題的關鍵是抓住box的每一次擴展，都對應地存在一個person的起始位置，兩者需要同時記錄參考:http:/...
閱讀全文
才儲©分析：您的性格類型傾向是“ ISFJ ”(內向 實感 情感 判斷)
沉靜，友善，有責任感和謹慎。能堅定不移地承擔責任。做事貫徹始終、不辭勞苦和準確無誤。忠誠，替人著想，細心；往往記著他所重視的人的種種微小事情，關心別人的感受。努力創造一個有秩序、和諧的工作和家居 環境。 ISFJ型的人忠誠、有奉獻精神和同情心，理解別人的感受。他們意志清醒而有責任心，樂于為人所需。 ISFJ型的人十分務實，他們喜歡平和謙遜的人。他們喜歡利用大量的事實情況，對于細節則有很強的記力。他們耐心地 對待任務的整個階段，喜歡事情能夠清晰明確。 ISFJ型的人具有強烈的職業道德，所以他們如果知道自己的行為真正有用時，會對需要完成之事承擔責任。他們準確系統地完成任務。他們具有傳統的價值觀，十分保守。他 們利用符合實際的判斷標準做決定，通過出色的注重實際的態度增加了穩定性。 ISFJ型的人平和謙虛、勤奮嚴肅。他們溫和、圓通，支持朋友和同伴。他們樂于協助別人，喜歡實際可行地幫助他人。他們利用個人熱情與人 交往，在困難中與他人和睦相處。ISFJ型的人不喜歡表達個人情感，但實際上對于大多數的情況和事件都具有強烈的個人反應。他們關心、保護朋友，愿意為朋友獻身，他們有為他人服務的意識，愿意完成他們的責任和義務。 您適合的領域有：領域特征不明顯，較相關的如：醫護領域、消費類商業、服務業領域 您適合的職業有：（該類型可能存在的盲點見完整分析報告） · 內科醫生
· 營養師
· 圖書/檔案管理員
· 室內裝潢設計師
· 顧客服務代表
· 記賬員
· 特殊教育教師
· 酒店管理
· 人事管理人員
· 電腦操作員
· 信貸顧問
· 零售業主
· 房地產代理或經紀人
· 藝術人員
· 商品規劃師
· 語言病理學者
· 審計師
· 會計
· 財務經理
· 辦公室行政管理
· 后勤和供應管理
· 中層經理
· 公務（法律、稅務）執行人員
· 銀行信貸員
· 成本估價師
· 保險精算師
· 稅務經紀人
· 稅務檢查員
· 機械、電氣工程師
· 計算機程序員
· 數據庫管理員
· 地質
· 氣象學家
· 法律研究者
· 律師
· 外科醫生
· 藥劑師
· 實驗室技術人員
· 牙科醫生
· 醫學研究員
from: http://www.apesk.com/mbti/dati.asp |
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3411思路:
做過幾道類似的題，DFS
不過，這一道有點特殊，每條邊以及每個點的訪問次數并非只有一次，為了能夠預付款，需要重復訪問某個點或者邊
這樣出現的一個問題就是搜索何時結束？這里參考了網上的代碼: 重復訪問的原因是為了能夠預先到達某個城市，而城市的總個數為N，也就是說，每個點的重復訪問次數不需要超過N
另外，由于每兩個點之間可能存在多條路徑，因此不能使用鄰接矩陣，而需要鄰接表
代碼
1 int N, m;
2 int min;
3 int mark[MAX_LEN];
4 struct Node {
5 int dest;
6 int adv;
7 int p, r;
8 struct Node *next;
9 };
10 struct Node *roads[MAX_LEN];
11 struct Node save[MAX_LEN];
12
13 void
14 init()
15 {
16 int i, a, b, c, p, r, cnt = 0;
17 min = INF;
18 memset(mark, 0, sizeof(mark));
19 memset(roads, 0, sizeof(roads));
20 for(i=0; i<m; i++) {
21 scanf("%d %d %d %d %d", &a, &b, &c, &p, &r);
22 save[cnt].dest = b;
23 save[cnt].adv = c;
24 save[cnt].p = p;
25 save[cnt].r = r;
26 save[cnt].next = roads[a];
27 roads[a] = save+cnt;
28 ++cnt;
29 }
30 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190思路:
DFS+減枝，好題
代碼:
1 /*
2 * N = R[1]^2*H[1] + R[2]^2*H[2] + 
+ R[M]^2*H[M]
3 * S = R[1]^2 + 2R[1]*H[1] + 2R[2]*H[2] + + 2R[M]H[M]
4 */
5 #include<stdio.h>
6 #include<stdlib.h>
7 #include<string.h>
8 #include<math.h>
9 #define MAX_LEVEL 21
10 #define INF 0x7FFFFFFF
11 /* from top level to the i[th] level, the minimum total volumn and area */
12 int min_volumn[MAX_LEVEL], min_area[MAX_LEVEL];
13 int n, m;
14 int rt;
15
16 void
17 init()
18 {
19 int i;
20 rt = INF;
21 min_volumn[0] = min_area[0] = 0;
22 for(i=1; i<MAX_LEVEL; i++) {
23 min_volumn[i] = min_volumn[i-1] + i*i*i;
24 min_area[i] = min_area[i-1] + 2*i*i;
25 }
26 }
27
28 /* from bottom(m[th] level) to the top */
29 void
30 dfs(int level, int last_r, int last_h, int cur_volumn, int cur_area)
31 {
32 int r, h, tmp, v, a;
33 if(cur_volumn+min_volumn[level]>n || cur_area+min_area[level]>=rt)
34 return;
35 /* ADD this pruning according the volumn&area formula */
36 if(2*(n-cur_volumn)/last_r+cur_area >= rt)
37 return;
38 if(level==0) {
39 if(cur_volumn == n)
40 rt = cur_area<rt ? cur_area : rt;
41 return;
42 }
43 /* the minimal r in [level] would be level */
44 for(r=last_r-1; r>=level; r--) {
45 tmp = (int)((n-cur_volumn-min_volumn[level-1])/(double)(r*r));
46 tmp = tmp>(last_h-1) ? (last_h-1) : tmp;
47 for(h=tmp; h>=level; h--) {
48 v = r*r*h;
49 a = 2*r*h;
50 if(level == m)
51 a += (r*r);
52 dfs(level-1, r, h, cur_volumn+v, cur_area+a);
53 }
54 }
55 }
56
57 int
58 main(int argc, char **argv)
59 {
60 int max_m_r, max_m_h;
61 while(scanf("%d %d", &n, &m) != EOF) {
62 init();
63 max_m_r = (int)(sqrt((n-min_volumn[m-1])/(double)m)) + 1;
64 max_m_h = (int)((n-min_volumn[m-1])/(double)(m*m)) + 1;
65 dfs(m, max_m_r, max_m_h, 0, 0);
66 if(rt == INF)
67 printf("0\n");
68 else
69 printf("%d\n", rt);
70 }
71 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1724思路:
有點與PKU 3256類似的題
第一個想法就是深搜
第一遍代碼(WA):
對于discuss里的測試數據該代碼是沒有問題的，可結果還是WA...
1 #define MAX_CITIES 101
2 #define INF 100000
3 int road[MAX_CITIES][MAX_CITIES];
4 int length[MAX_CITIES][MAX_CITIES];
5 int toll[MAX_CITIES][MAX_CITIES];
6 int visited[MAX_CITIES];
7 int k, n, r;
8 int min_len;
9
10 void
11 dfs(int city, int cur_len, int cur_toll)
12 {
14 int i;
15 visited[city] = 1;
16 if(cur_len>=min_len || cur_toll>k) {
17 visited[city] = 0;
18 return;
19 }
20 if(city == n) {
21 min_len = cur_len;
22 visited[city] = 0;
23 return;
24 }
25 for(i=1; i<=n; i++) {
26 if(road[city][i] && !visited[i])
27 dfs(i, cur_len+length[city][i], cur_toll+toll[city][i]);
28 }
29 visited[city] = 0;
30 }
繼續翻查discuss里，發現有人說兩點之間可能有多條路徑...
然后看到其他人代碼是使用鏈表來保存所有的路徑，所以修改后的AC代碼如下:
1 #define MAX_CITIES 101
2 #define INF 100000
3 struct Node {
4 int dest;
5 int len;
6 int toll;
7 struct Node *next;
8 };
9 struct Node roads[MAX_CITIES];
10 struct Node backup[MAX_CITIES*MAX_CITIES];
11 int visited[MAX_CITIES];
12 int k, n, r;
13 int min_len;
14
15 void
16 dfs(int c, int cur_len, int cur_toll)
17 {
18 int i;
19 struct Node *node;
20 if(cur_len>=min_len || cur_toll>k)
21 return;
22 if(c == n) {
23 min_len = cur_len;
24 return;
25 }
26 for(node=roads[c].next; node!=NULL; node=node->next) {
27 if(!visited[node->dest]) {
28 visited[node->dest] = 1;
29 dfs(node->dest, cur_len+node->len, cur_toll+node->toll);
30 visited[node->dest] = 0;
31 }
32 }
33 }
34
35 int
36 main(int argc, char **argv)
37 {
38 int i, s, d, l, t, cnt=0;
39 memset(visited, 0, sizeof(visited));
40 scanf("%d", &k);
41 scanf("%d", &n);
42 scanf("%d", &r);
43 for(i=1; i<=n; i++)
44 roads[i].next = NULL;
45 for(i=0; i<r; i++) {
46 scanf("%d %d %d %d", &s, &d, &l, &t);
47 backup[cnt].dest = d;
48 backup[cnt].len = l;
49 backup[cnt].toll = t;
50 backup[cnt].next = roads[s].next;
51 roads[s].next = backup+cnt;
52 ++cnt;
53 }
54 min_len = INF;
55 visited[1] = 1;
56 dfs(1, 0, 0);
57 if(min_len == INF)
58 printf("-1\n");
59 else
60 printf("%d\n", min_len);
61 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3373參考:
http://blog.csdn.net/logic_nut/archive/2009/10/29/4740951.aspxhttp://iaml.is-programmer.com/posts/8249.html (這個應該是SYSU的哈哈，里面有西西里)
思路:
這個題是真不會做，即使是看別人代碼都看了快兩天，艾...
首先要解決的問題是如何求大數的模(這里大數用字符串表示)？
我們知道對于取模運算有: (a+b)%k = ((a%k)+(b%k))%k
(ab)%k = ((a%k)(b%k))%k
對于0-9的每個數，可以將其在個、十、百、千...位時模k的結果保存到一張表中: mod_arr
這樣，修改這個大數的任何一位而模k的新結果可以在O(1)時間內取得
1 char num[MAX_LEN];
2 int hash[MAX_MOD];
3 int mod_arr[MAX_LEN][10];
4 int k, len, tmp[MAX_LEN], tmp2[MAX_LEN], start_mod;
5 int head, tail;
6 struct EACH {
7 int digits[MAX_LEN];
8 int remainder;
9 int index;
10 } queue[MAX_MOD];
11
12 void
13 init()
14 {
15 int i, j;
16 len = strlen(num);
17 for(j=0; j<10; j++)
18 mod_arr[0][j] = j%k;
19 for(i=1; i<len; i++)
20 for(j=0; j<10; j++)
21 mod_arr[i][j] = (mod_arr[i-1][j]*10)%k;
22 start_mod = 0;
23 for(i=0; i<len; i++) {
24 tmp[i] = tmp2[i] = num[len-i-1]-'0';
25 start_mod += (mod_arr[i][num[len-i-1]-'0']);
26 }
27 start_mod %= k;
28 head = -1;
29 tail = 0;
30 memset(hash, 0, sizeof(hash));
31 memset(queue, 0, sizeof(queue));
32 }
第一篇參考鏈接里是用DFS來做的，可惜我對于其中用于記憶化搜索的remember數組始終不理解，結果TLE
更加容易理解的方案是BFS，每次擴展改變一位數字
使用BFS的問題是如何判重？參考第二篇文章(繁瑣的C++語法，沒認真看呵呵)，使用余數判重，其實還不是太理解
代碼:
1 void
2 bfs()
3 {
4 int i, j, t, cur_rem, cur_index;
5 queue[tail].remainder = start_mod;
6 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
7 queue[tail].index = len-1;
8 hash[start_mod] = 1;
9 while(head < tail) {
10 ++head;
11 cur_rem = queue[head].remainder;
12 cur_index = queue[head].index;
13 memcpy(tmp, queue[head].digits, sizeof(int)*len);
14 if(cur_rem == 0) {
15 for(i=len-1; i>=0; i--)
16 printf("%d", tmp[i]);
17 printf("\n");
18 return;
19 }
20 /* changing digits: from least (smaller than itself) */
21 for(i=cur_index; i>=0; i--) {
22 for(j=0; j<tmp2[i]; j++) {
23 if(i==len-1 && j==0)
24 continue;
25 t = cur_rem + mod_arr[i][j] - mod_arr[i][tmp2[i]] + k; /* O(1) to find the new remainder */
26 t = t % k;
27 tmp[i] = j;
28 if(!hash[t]) {
29 ++tail;
30 queue[tail].remainder = t;
31 queue[tail].index = i-1;
32 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
33 hash[t] = 1;
34 }
35 }
36 tmp[i] = tmp2[i];
37 }
38 /* changing digits: to max (greater than itself) */
39 for(i=0; i<=cur_index; i++) {
40 for(j=tmp2[i]+1; j<10; j++) {
41 t = cur_rem + mod_arr[i][j] - mod_arr[i][tmp2[i]] + k;
42 t = t % k;
43 tmp[i] = j;
44 if(!hash[t]) {
45 ++tail;
46 queue[tail].remainder = t;
47 queue[tail].index = i-1;
48 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
49 hash[t] = 1;
50 }
51 tmp[i] = tmp2[i];
52 }
53 }
54 }
55 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2676思路:
深度搜索
純粹按照題意進行搜索，1532MS...額...就快TLE了呵呵
據discussion說，倒過來搜索時間會相當快
代碼:
1 #define MAX_LEN 10
2 char table[MAX_LEN][MAX_LEN];
3 int flag;
4
5 int
6 is_available(int x, int y, char ch)
7 {
8 int j, k, small_x, small_y;
9 for(j=0; j<9; j++) /* row */
10 if(table[x][j]==ch)
11 return 0;
12 for(k=0; k<9; k++) /* column */
13 if(table[k][y]==ch)
14 return 0;
15 small_x = x/3;
16 small_y = y/3;
17 for(j=small_x*3; j<(small_x+1)*3; j++)
18 for(k=small_y*3; k<(small_y+1)*3; k++)
19 if(table[j][k]==ch)
20 return 0;
21 return 1;
22 }
23
24 void
25 dfs(int x, int y)
26 {
27 int i, j, nx, ny;
28 if(flag)
29 return;
30 if(x==9){
31 if(!flag) {
32 for(j=0; j<9; j++)
33 printf("%s\n", table[j]);
34 flag = 1;
35 }
36 return;
37 }
38 if(y==8) {
39 nx = x+1;
40 ny = 0;
41 } else {
42 nx = x;
43 ny = y+1;
44 }
45 if(table[x][y] == '0') {
46 for(i=1; i<=9; i++) {
47 if(is_available(x, y, i+'0')) {
48 table[x][y] = i+'0';
49 dfs(nx, ny);
50 table[x][y] = '0';
51 }
52 }
53 } else
54 dfs(nx, ny);
55 }
更好的解題代碼見:
http://blog.csdn.net/logic_nut/archive/2009/08/09/4428996.aspx