搜索算法与图论(Week 4 , 5)

发布于 2022-11-21  251 次阅读


搜索和动态规划是算法界的两座大山。

搜索本质上是一种遍历,是对每一种情况操作一遍。

T1 迷宫(dfs)

是好题,一道用dfs的好题。

#include <iostream>
#include <cstring>
using namespace std;
int n,m,t;
int movex[5]={0,1,0,-1,0};//右 上
int movey[5]={0,0,-1,0,1};//左 下
int world[15][15];//图
int vis[15][15];//标记
int sx,sy,fx,fy;//起点 终点
int cnt;//计数。
void dfs(int x,int y){
	if(x==fx&&y==fy){
		cnt++;
		return;
	}
	for(int i=1;i<=4;i++){

		int nx=x+movex[i];
		int ny=y+movey[i];
		if(world[nx][ny]==1&&vis[nx][ny]==0){//可以走到。

			vis[nx][ny]=1;
			dfs(nx,ny);
			vis[nx][ny]=0;
		}
	}
}
int main(){
	memset(vis,0,sizeof(vis));
	memset(world,0x3f,sizeof(world));//默认不能走。
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			world[i][l]=1;//可以走的。
		}
	}
	cin>>sx>>sy>>fx>>fy;
	for(int i=1;i<=t;i++){
		int x1,y1;
		cin>>x1>>y1;
		world[x1][y1]=0x3f;//障碍。
	}
	vis[sx][sy]=1;
	dfs(sx,sy);
	cout<<cnt;
	return 0;
}

T2 马的遍历

是好题,一道用bfs的好题。

非常愚笨的手写队列。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2e5;
struct note{
	int x;//横坐标。
	int y;//纵坐标。
	int step;//步数。
};
note point[N];
int movex[9]={0,2, 2, 1, 1,-1,-1,-2,-2};
int movey[9]={0,1,-1, 2,-2, 2,-2, 1,-1};
int world[405][405];
int step[405][405];
bool vis[405][405];
int n,m;
int mx,my;
int main(){
	memset(world,0x3f,sizeof(world));//
	memset(step,0,sizeof(step));//特判
	cin>>n>>m;//输入N M。
	cin>>mx>>my;//输入起点。
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			world[i][l]=1;//能走的点。
		}
	}
	//step前+1 = step后。
	int head=1,tail=1;
	point[head].x = mx;
	point[head].y = my;//起点??
	vis[mx][my]=true;
	tail++;
	while(head<tail){
                        for(int i=1;i<=8;i++){
			int cur_x=point[head].x+movex[i];//移动后的横坐标。
			int cur_y=point[head].y+movey[i];//移动后的纵坐标。

			if(cur_x<=0||cur_y<=0) continue;//防止数组越界。
			if(world[cur_x][cur_y]==1&&vis[cur_x][cur_y]==false){//可以走 且 没走过。

				point[tail].x=cur_x;//记录横坐标。
				point[tail].y=cur_y;//记录纵坐标。
				vis[cur_x][cur_y]=true;//这个点已经走过了。
				step[cur_x][cur_y]=step[point[head].x][point[head].y]+1;//从开始遍历八个方向的点的STEP+1。
				tail++;//记录 入列。
//cout<<"step head: "<<step[point[head].x][point[head].y]<<endl;
//cout<<"step cur : "<<step[cur_x][cur_y]<<endl<<endl;
			}
		}
		head++;//遍历完成。
	}
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			if(step[i][l]==0){
				step[i][l]=-1;//仍然为0的点。
			}
		}
	}
	step[mx][my]=0;//起点为0。
	
	for(int i=1;i<=n;i++){
		for(int l=1;l<=m;l++){
			cout<<step[i][l]<<"    ";
		}
		cout<<endl;
	}
	return 0;
}

待续............。