我们经常使用的数的进制为“常数进制”，即始终逢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