首先是dfs，又名深度优先搜索。看名字就知道，它的核心思想就是一直搜索，先在一条路上面一路撸到底，如果到底没有办法前进了，那么判断是否到达终点，如果没有到达，那么就回溯到之前的点再撸。
dfs的要点：
1、考虑当下应该怎么做，在你现在的点上面你应该怎么做，可以怎么做。可以向上吗？可以向下吗？
2、后面的和前面一样的做。递归的思想。
3、要考虑边界，终点等题目给出的条件检测。过滤掉那些不需要的解。
4、利用适当的数据结构，保存当前点是否走过，保存走过的路线等。
模版：
void dfs(int step)
{
判断你的所有条件，如果不行直接return；
for（循环每一个方向）
｛
dfs（step+1）
｝
return；
}
map【】【】记录走过的地方，走过的记为1
可以尝试利用堆栈来存放记录
#include<cstdio> #include<cstdlib> #include<ctime> #include<iostream> using namespace std; int result[10]; int book[10]; int r=0; /*求九个不同的个位数组合满足，3位+3位=3位的题目，主要是记录一下dfs的模版*/ void dfs(int step) { if(step == 7)/*简单的优化一下*/ { int sum = result[1]*100 + result[4]*100 + result[2]*10 + result[5]*10 + result[3] + result[6]; if(book[sum%10] == 1) return; sum/=10; if(book[sum%10] == 1) return; sum/=10; if(book[sum%10] == 1) return; } if(step == 10) { if(result[1]*100 + result[4]*100 + result[2]*10 + result[5]*10 + result[3] + result[6] == result[7]*100 + result[8]*10 + result[9]) { printf("%d%d%d + %d%d%d = %d%d%d ",result[1],result[2],result[3],result[4],result[5],result[6],result[7],result[8],result[9]); r++; } return; } int i; for (i = 1; i <= 9; i++) { if(book[i] == 0) { result[step] = i; book[i] = 1; dfs(step+1); book[i] = 0; } } return; } int main() { clock_t start,finish; double duration; start = clock(); dfs(1); cout<<"-------------------"<<r<<endl; finish = clock(); duration = double(finish - start)/CLOCKS_PER_SEC; printf("time used:%f ms ",1000*duration); return 0; }
接下来是bfs，又名广度优先搜索，他是一个老实人，一步步走的很踏实，只有把n步的能走的地方走遍，才会走第n+1步，慢慢的拓展
要点：
1、用队列保存每一步走的结果，用一个字段去表示走的步数；
2、没有递归，利用while循环到最终结果；
3、时刻注意队列的首尾指针的位置；
模版：
while(head<tail)
{
for(循环所有方向)
{
把坐标进行改变，改成now的坐标，意思就是走一步
判断所有不可能的情况，不可能就continue
标记走过了
在队列中加入这个走过的点和步数
*****tail++*****
}
*****head++*****
}
#include<cstdio> #include<cstdlib> #include<ctime> #include<iostream> using namespace std; /*首先定义方向数组*/ /* X/Y 0/-1 -1/0 0/0 1/0 0/1 右下左上*/ int way[4][2] = { {1,0},//右 {0,1},//下 {-1,0},//左 {0,-1}//上 }; int map[50][50]; int book[50][50]; int n,m; int head=0; int tail=0; int flag=0; struct que { int x; int y; int stpe; }; struct que q[2500]; int main() { int x,y; cin>>n>>m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin>>map[i][j]; } } head = 1; tail = 1; q[tail].x = 1; q[tail].y = 1; q[tail].stpe = 0; tail++; book[1][1] = 1; flag = 0; while (head<tail) { for (int i = 0; i < 3; i++) { x = q[head].x + way[i][0]; y = q[head].y + way[i][1]; if(x<1 || y < 1 || x > n || y > m) continue; if(map[x][y] == 0 && book[x][y] == 0) { q[tail].x = x; q[tail].y = y; q[tail].stpe = q[head].stpe + 1; tail++; book[x][y] = 1; } if(x == 4 && y == 3) { printf("--------------------%d ",q[tail-1].stpe); return 0; } } head++; } return 0; }
主要是记录一下两钟搜索的模版，具体两种搜索的使用还要在实际中进行检验，对于迷宫的题目只是现在肯定不会迷茫了，之后对于图的遍历还有别的，对于两种搜索的比较取舍，之后再写吧。