貪吃蛇--dfs與bfs初步學習

標題 貪吃蛇–dfs與bfs對比學習（適合初學小白）

題目地址
貪吃蛇 link
https://ac.nowcoder.com/acm/contest/9986/I
鏈接：https://ac.nowcoder.com/acm/contest/9986/I
來源：牛客網

題目描述
無限增長的貪吃蛇小游戲：

在一個n*m的迷宮中，有一條小蛇，地圖中有很多圍墻，猥瑣的出題者用“#”表示，而可以走的路用“.”表示，小蛇他隨機出生在一個點上，出生點表示為“S”，他想抵達的終點表示為“E”，小蛇有一個奇怪的能力，他每走一格便會增長一格，即他走了一格后，他的尾巴不會碩訓，

小蛇想知道他怎么到達他想去的地方，請你幫助他，

PS：每格長1米，貪吃蛇規定不能撞墻，不能咬自己的身體，
輸入描述:
第一行：輸入N,M；

第二行：輸入S的坐標Xs，Ys，E的坐標Xe，Ye;

后面的N行：

每行輸入M個數，描述每一行的情況，

輸出描述:
輸出一個數，小蛇到達終點的最短距離（單位：cm），若無法達到，輸出-1
示例1
輸入
復制
3 3
1 1 3 3
.#.
.#.
…
輸出
復制
400
示例2
輸入
復制
5 5
1 1 5 5
…###
.#…
.#.#.
.#.#.
…#.
輸出
復制
1400
備注:
對于 100% 的資料：1\le n,m\le 1001≤n,m≤100 ，保證起點不是圍墻，

思路
*1.*bfs與dfs都可以解決，但是不同的方式都會遇見相同的問題：距離怎么表示，如何求最近的距離
*2.*對于bfs 他每一次將可以移動的地方記錄下來，也就是說一個點到周圍可以移動的點他都會先遍歷一遍，然后再走，所以我們可以吧vis陣列改一下（本來是用來記錄是否走過，防止來回移動），將他改成在記錄改點的距離的資料，也就是說vis是記錄這個點是起點移動幾步得到的，
代碼如下：

#include<bits/stdc++.h>
using namespace std;
const int M = 110;
int vis[110][110];
int m,n,xs,ys,ye,xe,ok; //初始資料 
char Map[110][110];
struct node{
	int xx;
	int yy; 
};//表示坐標 
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
void bfs(){
	queue<node> q;
	node beg,ll;//beg是將起點變成node的型別，不然queue不認識，見面就打架
				//ll也是轉換，就是新得到出來的點 轉換，詳情往下看 
	beg.xx=xs;
	beg.yy=ys;
	q.push(beg);
	vis[xs][ys] = 0;
	while(!q.empty()){
		node top = q.front();
		q.pop();
		if(top.xx==xe&&top.yy==ye) {
			ok = 1;
			return ;
		}
		for(int i = 0;i<4;i++){
			int xx = top.xx+dx[i];
			int yy = top.yy+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
				if(vis[xx][yy] == -1&&Map[xx][yy]!='#'){
				vis[xx][yy] = vis[top.xx][top.yy]+1; //與普通bfs區別 就在這，沒錯，理解這里就okk了， 
				ll.xx = xx;
				ll.yy = yy;
				q.push(ll);
				}
			}
		}	
	}
	
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&xs,&ys,&xe,&ye);
	for(int i = 1;i<=n;i++){
		scanf(" ");
		for(int j = 1;j<=m;j++)
		scanf("%c",&Map[i][j]);
	}
	memset(vis,-1,sizeof vis);
	bfs();
	if(!ok) cout<<-1<<endl;
	else
	cout<<(vis[xe][ye])*100<<endl;
	return 0;
}

哎呀，說那么多，其實只要理解了vis[xx][yy] = vis[top.xx][top.yy]+1就可以明白了，
*3.*dfs要注意一條路走過之后，還能被另一種方案走，也就是一個點可能被用多次，所有當這個點遍歷完，還是要出來的，
代碼如下

#include<bits/stdc++.h>
using namespace std;
int n,m,xs,ys,xe,ye; //初始讀入 
const int INF  = 0x4f4f4f4f; //設定最大值 
int vis[110][110];  //記錄是否走過
char Map[110][110]; 
struct node{
	int xx,yy;
	bool operator==(const node& nw){	//定義 相等 
		return (nw.xx==xx&&nw.yy==yy);  
	}
}be,en; //起點和終點 
int maxs = INF,ok;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(node t,int dis){
	if(t == en){
		maxs = min(dis,maxs);
		ok = 1; 
	}
	int xx,yy;
	vis[t.xx][t.yy] = 1; 
	for(int i = 0;i<4;i++){
		xx = t.xx+dx[i];
		yy = t.yy+dy[i];
		if(xx>0&&xx<=n&&yy>0&&yy<=m&&vis[xx][yy]==0&&Map[xx][yy]!='#'){
			node go;
			go.xx=xx;
			go.yy=yy;
			vis[xx][yy] = 1; 
			dfs(go,dis+1);
			//與簡單的dfs區別就是這了，沒錯！！！ 
			vis[xx][yy] = 0; //出來后表示回去，因此這條路也就不能算走過了 
		}
	}

}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%d%d%d%d",&xs,&ys,&xe,&ye);
	be.xx = xs;
	be.yy = ys;
	en.xx = xe;
	en.yy = ye;
	for(int i = 1;i<=n;i++){
		scanf(" ");
		for(int j = 1;j<=m;j++){
			scanf("%c",&Map[i][j]);
		}
	}
	dfs(be,0);
	
	if(ok)
	cout<<maxs*100<<endl;
	else cout<<-1<<endl;
	return 0;
} 

又到了讓我期待的 總結
對比上面兩個代碼，會發現，bfs只要第一次找到了出口，就是最短的距離，而dfs還是要跑完整張圖，可能有優化方法我沒想到，，，
總而言之，建議在于最短路程相關的遍歷時還是用bfs更好，更方便，