备战蓝桥杯——dfs、求无权图最短路径

备战蓝桥杯——dfs、求无权图最短路径_BFS

本文主要是介绍备战蓝桥杯——dfs、求无权图最短路径_BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

例：走迷宫最短路
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int m,n;
char mp[50][50];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool vis[50][50]; //判断这个点是否已经被搜索过  点集X
//PII F; //点集F的类型
struct node {int x,y,d;node(int xx,int yy,int dd){x=xx;y=yy;d=dd;}
};
bool in(int x,int y){return 0<=x&&x<n&&0<=y&&y<m;
}int bfs(int x,int y){int step=0;// queue<PII> F;//点集F的类型PII==pair<int,int> 是一个类型queue<node> F;//F.push({x,y});F.push(node(x,y,0)); //放入第一个起点vis[x][y]=true;  //遍历过，标记，即放到X点集中while(!F.empty()){// PII now=F.front();  //访问队首元素，队首元素类型是PIInode now=F.front();F.pop(); //弹出队首,即从点集F中取出了一个点v//处理点v,即遍历四个邻居,看是否合法，把点v加入点集X，这一步在开始就做过了for(int i=0;i<4;i++){//int tx=now.first+dir[i][0];//int ty=now.second+dir[i][1];int tx=now.x+dir[i][0];int ty=now.y+dir[i][1];if(in(tx,ty) && mp[tx][ty]!='*' && !vis[tx][ty]){if (mp[tx][ty]=='T'){return now.d+1;  //邻居点是走过了的}else{vis[tx][ty]=true; //xx,yy点就是下一个起点，放进队列中F.push(node(tx,ty,now.d+1));//进队列F，即将这个点放进点集F中}}}}return -1;//没找到
}
int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>mp[i];}int sx,sy;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mp[i][j]=='S'){sx=i;sy=j;}}}int res=bfs(sx,sy);cout<<res;return 0;
}

#include <iostream>
using namespace std;
const int N=1e5;int n,t,res;
int mp[N];
bool vis[N];  //已经处理的点集Xvoid dfs(int x,int ans){//出口if(vis[x]){ //如果这个点之前访问过if(mp[x]==mp[t]){  //如果回到起点if(ans>res){  //更新最小路径res=ans; }}return;}///否则继续递归vis[x]=1;dfs(mp[x],ans+1);vis[x]=0;
}int main()
{// 请在此输入您的代码cin>>n;for(int i=1;i<=n;i++){cin>>mp[i];}for(int i=1;i<=n;i++){t=i;dfs(i,0);  //遍历每一个起点    }cout<<res;return 0;
}