登录以参加训练计划

模板

深度优先搜索 dfs

#include <bits/stdc++.h>
using namespace std;
//                 1 2 3 4 5 6 7 8 9 10111213
int mp[14][14]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,1,0,0,0,1,0,0,1,0,0,0},
				{0,0,1,1,0,1,1,1,1,0,1,0,1,0},
		 		{0,0,0,0,0,0,0,1,0,0,0,0,1,0},
				{0,0,1,0,1,1,0,1,1,0,1,0,0,0},
				{0,0,1,0,1,0,0,0,0,0,1,1,1,0},
				{0,1,1,0,1,1,1,0,1,0,1,0,0,0},
				{0,0,0,0,1,0,0,0,1,0,0,0,1,0},
				{0,0,1,1,1,0,1,1,1,0,1,1,1,0},
				{0,0,1,0,0,0,1,0,0,0,0,0,1,0},
				{0,0,1,0,1,0,1,1,0,1,1,0,1,0},
				{0,0,0,0,1,0,0,0,0,1,0,0,1,0},
				{0,0,1,1,1,1,1,0,1,1,0,1,1,0},
				{0,0,0,1,0,0,0,0,1,0,0,0,0,0},};
int vis[14][14];//vis[i][j]=0 没走过 1走过  
int n=13,m=13;
int fx=3,fy=1,sx=10,sy=13;
int cnt=0;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int ans=0;

void dfs(int x,int y,int len){//位置 x y
	if(x==sx&&y==sy){//终点 
		cnt++;
		ans=max(ans,len);
		return ;
	}
	// i=2 下 
	for(int i=0;i<=3;i++){
		int tx=x+dx[i],ty=y+dy[i];
		if(tx>=1 && tx<=n && ty>=1 && ty<=m && mp[tx][ty]==0 && vis[tx][ty]==0){//不出界  不是障碍 不能走过 
			vis[tx][ty]=1;
			dfs(tx,ty,len+1);
			vis[tx][ty]=0; 
		}	
	}		
}


int main(){
	vis[fx][fy]=1; 
	dfs(fx,fy,0);
	cout<<cnt;
}




//	//上  tx=x+-1  ty=y+0  tx=x+dx[0]  ty=y+dy[0]
//	{
//		int tx=x+dx[0],ty=y+dy[0];
//		if(tx>=1 && tx<=n && ty>=1 && ty<=m && mp[tx][ty]==0 && vis[tx][ty]==0){//不出界  不是障碍 不能走过 
//			vis[tx][ty]=1;
//			dfs(tx,ty);
//			vis[tx][ty]=0; 
//		}	
//	}
//	//右  tx=x+0  ty=y+1 tx=x+dx[1]  ty=y+dy[1]
//	{
//		int tx=x+dx[1],ty=y+dy[1];
//		if(tx>=1 && tx<=n && ty>=1 && ty<=m && mp[tx][ty]==0 && vis[tx][ty]==0){//不出界  不是障碍 不能走过 
//			vis[tx][ty]=1;
//			dfs(tx,ty);
//			vis[tx][ty]=0; 
//		}	
//	}
//	//下  tx=x+1  ty=y+0 tx=x+dx[2]  ty=y+dy[2]
//	{
//		int tx=x+dx[2],ty=y+dy[2];
//		if(tx>=1 && tx<=n && ty>=1 && ty<=m && mp[tx][ty]==0 && vis[tx][ty]==0){//不出界  不是障碍 不能走过 
//			vis[tx][ty]=1;
//			dfs(tx,ty);
//			vis[tx][ty]=0; 
//		}	
//	}
//	//左  tx=x+0  ty=y+-1 tx=x+dx[3]  ty=y+dy[3]
//	{
//		int tx=x+dx[3],ty=y+dy[3];
//		if(tx>=1 && tx<=n && ty>=1 && ty<=m && mp[tx][ty]==0 && vis[tx][ty]==0){//不出界  不是障碍 不能走过 
//			vis[tx][ty]=1;
//			dfs(tx,ty);
//			vis[tx][ty]=0; 
//		}	
//	}

广度优先搜索

bfs

#include <bits/stdc++.h>
using namespace std;
int n,m;
int mp[][];
int vis[][];
int fx,fy,sx,sy;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct ST{
	int x,y;
};
queue<ST>Q; 

int main(){
	memset(vis,-1,sizeof(vis));//初始化vis数组都为-1 
	
	Q.push({fx,fy});
	vis[fx][fy]=0;
	while(Q.size()>0){
		ST t=Q.front();
		Q.pop();
		if(t.x==sx&&t.y==sy){
			。。。。
			break; 
		}
		for(int i=0;i<=3;i++){
			int tx=t.x+dx[i];
			int ty=t.y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&mp[tx][ty]==0&&vis[tx][ty]==-1){
				vis[tx][ty]=vis[t.x][t.y]+1;
				Q.push({tx,ty});
			}
		}
	}
}