1.对1、2、3 ，3个数全排列（排列考虑顺序）
//万能的搜索－递归 dfs(1);
递归
int a[3],book[3],n=3; void dfs(int step) { //如果站在n+1个盒子面前，则表示前n个盒子已经放好的牌 if (step == n+1) { for (int i = 1; i <= n; i++) { printf("%d",a[i]); } printf(" "); return;//返回之前的一步（最近一次调用dfs函数的地方） } //step表示第step个盒子 for (int i = 1; i <= n; i++) { if (book[i] == 0) { a[step] = i; book[i] = 1;//该牌已经打出 dfs(step+1); book[i] = 0;//收回该牌 } } }
2.求到达目的地的最小步数
广度优先搜索(队列＋hashMap之类的去重集合)和深度优先搜索（递归）
int q = 3,p = 2,min = 1000; int book[51][51]; int myMap[51][51] = {{0,0,1,0}, {0,0,0,0}, {0,0,1,0}, {0,1,0,0}, {0,0,0,1}}; int next[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}}; void dfs(int x,int y,int step); struct note{ int x;//横坐标 int y;//纵坐标 int s;//步数 int f;//父亲在队列中的编号，本题不要求输出路径，可以不需要f }; int main(int argc, const char * argv[]) { @autoreleasepool { //1深度优先搜索 // dfs(0, 0, 0); // printf("min = %d ",min); //2广度优先搜索 struct note que[2501]; int head = 0,tail = 0; int tx,ty,flag = 0; que[tail].x = 0; que[tail].y = 0; que[tail].f = 0; que[tail].s = 0; tail++; book[0][0] = 1; while (head < tail) { for (int k = 0; k < 4; k++) { tx = que[head].x + next[k][0]; ty = que[head].y + next[k][1]; if (tx < 0 || ty < 0 || tx > 5 || ty > 4) { continue; } if (myMap[tx][ty]==0 && book[tx][ty]==0) { book[tx][ty] = 1; //插入新的点到队列中 que[tail].x = tx; que[tail].y = ty; que[tail].f = head; que[tail].s = que[head].s + 1; tail++; } //到达目的地 if (tx == q && ty == p) { flag = 1; break; } } if (flag==1) { break; } head++; } printf("dfd = %d ",que[tail-1].s); } return 0; } void dfs(int x,int y,int step) { int tx,ty;
//判断是否到达结束位置，结束递归 if (x == q && y == p) { if (step < min) { min = step; } return; } //遍历4个方向 for (int k = 0; k < 4; k++) {
//计算下一个点的坐标tx、ty tx = x + next[k][0]; ty = y + next[k][1]; //判断是否越界 if (tx < 0 || ty < 0 || ty > 5 || tx > 4) { continue; } //判断该点是否障碍物和已经走过 if (myMap[tx][ty] == 0 && book[tx][ty]==0) { book[tx][ty] = 1; dfs(tx, ty, step+1); book[tx][ty] = 0; } } }
3.炸弹人（求消灭敌人的最大个数）
3.1广度优先搜索实现
int next[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}}; int a[21][21] = { {'#','#','#','#','#','#','#','#','#','#','#','#','#'}, {'#','G','G','.','G','G','G','#','G','G','G','.','#'}, {'#','#','#','.','#','G','#','G','#','G','#','G','#'}, {'#','.','.','.','.','.','.','.','#','.','.','G','#'}, {'#','G','#','.','#','#','#','.','#','G','#','G','#'}, {'#','G','G','.','G','G','G','.','#','.','G','G','#'}, {'#','#','G','.','.','G','#','.','.','.','.','.','#'}, {'#','G','#','.','#','G','#','#','#','.','#','G','#'}, {'#','.','.','.','#','#','#','#','#','#','#','#','#'}, {'#','G','#','.','#','G','#','G','#','.','#','G','#'}, {'#','G','G','.','G','G','G','#','G','.','G','G','#'}, {'#','#','#','#','#','#','#','#','#','#','#','#','#'}}; struct note{ int x;//横坐标 int y;//纵坐标 int s;//步数 int f;//父亲在队列中的编号，本题不要求输出路径，可以不需要f }; int getnum(int i,int j);
.
//3广度优先搜索。用炸弹消灭最多的敌人G、.代表可走的路、＃代表墙 struct note que[401]; int head = 0,tail = 0; int book[20][20] = {0}; int sum,max,mx,my,tx,ty; que[tail].x = 3; que[tail].y = 3; tail++; book[3][3] = 1; max = getnum(3, 3); mx = 3; my = 3; while (head<tail) { for (int k = 0;k < 4; k++) { tx = que[head].x + next[k][0]; ty = que[head].y + next[k][1]; //判断是否越界 if (tx < 0 || ty < 0 || ty > 13 || tx > 12) { continue; } // if (a[tx][ty]=='.' && book[tx][ty]==0) { book[tx][ty] = 1; que[tail].x = tx; que[tail].y = ty; tail++; sum = getnum(tx, ty); printf("____h sum = %zd ",sum); if (sum>max) { max = sum; mx = tx; my = ty; } } } head++; } printf("haha = %d,%d ,count = %d",mx,my,max);
.
int getnum(int i,int j) { int sum = 0,x,y; x = i;y = j; while (a[x][y]!='#') { if (a[x][y]=='G') { sum++; } x--; } x = i;y = j; while (a[x][y]!='#') { if (a[x][y]=='G') { sum++; } x++; } x = i;y = j; while (a[x][y]!='#') { if (a[x][y]=='G') { sum++; } y--; } x = i;y = j; while (a[x][y]!='#') { if (a[x][y]=='G') { sum++; } y++; } return sum; }
3.2深度优先搜索实现
//深度优先搜索 book[3][3] = 1; max = getnum(3, 3); dfs(3, 3, 0); printf("haha = %d,%d ,count = %d",mx,my,max);
.
void dfs(int x,int y,int step) { int sum = getnum(x, y); if (sum > max) { max = sum; mx = x; my = y; } int tx,ty; for (int k = 0; k < 4; k++) { tx = x + next[k][0]; ty = y + next[k][1]; if (tx < 0 || ty < 0 || ty > 13 || tx > 12) { continue; } if (a[tx][ty]=='.' && book[tx][ty]==0) { book[tx][ty] = 1; dfs(tx, ty, step+1); } } }