搜索算法（一）

深度优先搜索（dfs)

深度优先的意思就是一条路走到黑，如果符合条件就一直走，否则就返回上一个节点

模板

#include<iostream> using namespace std; const int N=10; int ans[N]; bool mark[N]; int n; void dfs(int u) { //"回头"的条件 if(u==n) { for(int i=0;i<n;i++)cout<<ans[i]<<" "; puts(""); return; } for(int i=1;i<=n;i++) { if(mark[i]==false) { mark[i]=true; ans[u]=i; dfs(u+1); //复原 mark[i]=false; ans[u]=0; } } } int main() { cin>>n; dfs(0); return 0; }

广度优先搜索（bfs）

最短路

#include<iostream> #include<cstring> #include<queue> using namespace std; const int N=110; typedef pair<int,int> PII; int map[N][N],mark[N][N]; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},n,m,ans; void bfs() { memset(mark,-1,sizeof mark); queue<PII>q; q.push({0,0}); mark[0][0]=0; while(!q.empty()) { PII top=q.front(); for(int i=0;i<4;i++) { int nex=top.first+dx[i],ney=top.second+dy[i]; if(nex>=0&&nex<n&&ney>=0&&ney<m&&mark[nex][ney]==-1&&map[nex][ney]==0) { mark[nex][ney]=mark[top.first][top.second]+1; q.push({nex,ney}); } } q.pop(); } cout<<mark[n-1][m-1]; } int main() { cin>>n>>m; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",&map[i][j]); } } bfs(); }