第四章 搜索（深度、广度搜索、全排列、走迷宫、再解炸弹人、宝岛探险、水管工游戏）

 1 //输入一个数n
 2 //输出1-n的全排列
 3 #include <stdio.h>
 4 int n, book[10], a[10];
 5 void dfs(int step)
 6 {
 7     int i;
 8     if (step > n)
 9     {
10         for (i = 1;i <= n;i++)
11         {
12             printf("%d ",a[i]);
13         }
14         printf("\n");
15         return;
16     }
17     for (i = 1;i <= n;i++)
18     {
19         if (book[i] == 0)
20         {
21             a[step] = i;
22             book[i] = 1;
23             dfs(step+1);
24             book[i] = 0;
25         }
26     }
27     return;
28 }
29 int main()
30 {
31     scanf("%d",&n);
32     dfs(1);
33     return 0;
34 }

 1 #include <stdio.h>
 2 int total = 0;
 3 int book[10], a[10];
 4 void dfs(int step)
 5 {
 6     int i;
 7     if (step == 10)
 8     {
 9         if (100 * (a[1] + a[4]) + 10 * (a[2] + a[5]) + a[3] + a[6] == 100 * a[7] + 10 * a[8] + a[9])
10         {
11             total++;
12             printf("%d%d%d + %d%d%d = %d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
13         }
14         return;
15     }
16     for (i = 1;i < 10;i++)
17     {
18         if (book[i] == 0)
19         {
20             book[i] = 1;
21             a[step] = i;
22             dfs(step+1);
23             book[i] = 0;
24         }
25     }
26     return;
27 }
28 int main()
29 {
30     dfs(1);
31     printf("%d\n",total/2);
32     return 0;
33 }

 1 #include <stdio.h>
 2 int n, m, map[10][10], book[10][10],endx, endy,minstep=978978;
 3 void dfs(int x, int y, int step)
 4 {
 5     int i,tx,ty;
 6     int next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
 7     if (x == endx&&y == endy)
 8     {
 9         if (minstep > step)
10             minstep = step;
11         return;
12     }
13     for (i = 0;i < 4;i++)
14     {
15         tx = x + next[i][0];
16         ty = y + next[i][1];
17         if (tx<1 || ty<1 || tx>n || ty>m)
18             continue;
19         if (map[tx][ty] == 0 && book[tx][ty] == 0)
20         {
21             book[tx][ty] = 1;
22             dfs(tx,ty,step+1);
23             book[tx][ty] = 0;
24         }
25     }
26     return;
27 }
28 int main()
29 {
30     int i, j, startx, starty;
31     scanf("%d%d",&n,&m);
32     for (i = 1;i <= n;i++)
33     {
34         for (j = 1;j <= m;j++)
35         {
36             scanf("%d",&map[i][j]);
37         }
38     }
39     scanf("%d%d%d%d",&startx,&starty,&endx,&endy);
40 
41     dfs(startx,starty,0);
42     
43     printf("%d\n",minstep);
44     return 0;
45 }

 1 #include <stdio.h>
 2 int n, m, endx, endy;
 3 int map[10][10], book[10][10];
 4 struct node
 5 {
 6     int x;
 7     int y;
 8     int step;
 9 };
10 void bfs(int startx,int starty)
11 {
12     struct node queue[100];
13     int head, tail;
14     int next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
15     int i, tx, ty, flag = 0;
16     head = 1;tail = 1;
17     queue[tail].x = startx;
18     queue[tail].y = starty;
19     queue[tail].step = 0;
20     tail++;
21     book[startx][starty] = 1;
22     while (head<tail)
23     {
24         for (i = 0;i < 4;i++)
25         {
26             tx = queue[head].x + next[i][0];
27             ty = queue[head].y + next[i][1];
28             if (tx<1 || ty<1 || tx>n || ty>m)
29             {
30                 continue;
31             }
32             if (map[tx][ty] == 0 && book[tx][ty] == 0)
33             {
34                 book[tx][ty] = 1;
35                 queue[tail].x = tx;
36                 queue[tail].y = ty;
37                 queue[tail].step = queue[head].step + 1;
38                 tail++;
39             }
40             if (tx == endx&&ty == endy)
41             {
42                 flag = 1;
43                 break;
44             }
45         }
46         if (flag == 1)
47             break;
48         head++;
49     }
50     printf("%d\n",queue[tail-1].step);
51 
52 }
53 int main()
54 {
55     int i, j,startx,starty;
56     scanf("%d%d",&n,&m);
57     for (i = 1;i <= n;i++)
58     {
59         for (j = 1;j <= m;j++)
60         {
61             scanf("%d",&map[i][j]);
62         }
63     }
64     scanf("%d%d%d%d",&startx,&starty,&endx,&endy);
65     bfs(startx,starty);
66     return 0;
67 }