首页 > 其他分享 >迷宫2

迷宫2

时间:2023-03-24 16:00:25浏览次数:28  
标签:ny int 迷宫 nx vis continue now

题意

样例输入:
3 3 2
0 0 0
0 1 0
0 0 0
3 3
3 1
1 1
样例输出:
6
数据范围:
对于10%的数据,N,M<=4,K<=1。
对于30%的数据,N,M<=10。
对于60%的数据,N,M<=100。
对于100%的数据,N,M<=1000,K<=10。

解析

多轮bfs,每轮统计当前这轮的最短步数。
类似时间戳。
每轮可以走当前这个点,其他的记录点不能走

代码

//std
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int x[15],y[15],sx,sy,ex,ey,n,m,k;
int g[N][N],d[N][N],vis[N][N],ans;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

struct node{
	int x,y,step;
};



int bfs(int time){
	queue<node> q;
	vis[sx][sy] = time;
	q.push({sx,sy,0});
	
	while(q.size()){
		node now = q.front();
		q.pop();
		
		if(now.x == ex && now.y == ey){
			return now.step;
		} 
		
		for(int i = 0; i < 4; i ++ ){
			int nx = now.x + dx[i];
			int ny = now.y + dy[i];
			
			if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
			if(g[nx][ny] == 1) continue;
			if(d[nx][ny] == 1) continue;
			if(vis[nx][ny] == time) continue;
			vis[nx][ny] = time;
			q.push({nx,ny,now.step + 1});
			
		}
	}
	return -1;
}

int main(){
	scanf("%d %d %d",&n,&m,&k);
	
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= m; j ++ ){
			scanf("%d",&g[i][j]);
		}
	} 
	
	//先要把所有点存下来 才能知道有没有经过后面的记录点 
	for(int i = 1; i <= k; i ++ ){
		scanf("%d %d",&x[i],&y[i]);
		d[x[i]][y[i]] = 1;
	}
	
	scanf("%d %d",&sx,&sy);
	
	for(int i = 1; i <= k; i ++ ){
		//每次当前这个点可以走 别的记录点不能走 
		d[x[i]][y[i]] = 0;
		ex = x[i],ey = y[i];
		 
		 
		int tmp = bfs(i);
		if(tmp >= 0){
			ans += tmp;//总步数 加上 当前走的步数 
		}else{
			//某次到不了某个点 就结束
			cout << - 1;
			return 0;
		}
		
		sx = x[i],sy = y[i];
		d[x[i]][y[i]] = 1;
	} 
	
	cout << ans; 
	
	return 0;
}

标签:ny,int,迷宫,nx,vis,continue,now
From: https://www.cnblogs.com/dtdbm/p/17252285.html

相关文章

  • 迷宫1
    bfs最短路径有几条题意样例输入:4...S.XX..XX.E...样例输出:62数据范围:1≤n≤25解析path数组记录点代码#include<bits/stdc++.h>usingnamespacestd;......
  • 蓝桥杯之迷宫
    蓝桥杯题解迷宫下图给出了一个迷宫的平面图,其中标记为11的为障碍,标记为00的为可以通行的地方。010000000100001001110000迷宫的入口为左上角,出口为右下角,在迷......
  • 迷宫
    迷宫-蓝桥云课(lanqiao.cn)publicclassN602{ staticchar[][]m=newchar[30][50]; staticchar[]d={'D','L','R','U'};//定义这个顺序为字典序答案就......
  • 迷宫问题之bfs
    先来一道简单的迷宫模板题迷宫由n行m列的单元格组成,每个单元格要么是空地,要么是障碍物。其中1表示空地,可以走通,2表示障碍物。输出从左上角到右下角的最短路径长度。......
  • bfs走迷宫
      #include<iostream>#include<cstring>#include<queue>constintN=110;intn,m;typedefpair<int,int>PII;intg[N][N];//存图intd[N][N];//记录距离PIIq......
  • 基于形态学处理算法的迷宫路线搜索matlab仿真
    1.算法描述形态学是图像处理中应用最为广泛的技术之一,主要用于从图像中提取对表达和描绘区域形状有意义的图像分量,使后续的识别工作能够抓住目标对象最为本质的形状特征,如......
  • 基于形态学处理算法的迷宫路线搜索matlab仿真
    1.算法描述       形态学是图像处理中应用最为广泛的技术之一,主要用于从图像中提取对表达和描绘区域形状有意义的图像分量,使后续的识别工作能够抓住目标对象最为本......
  • 迷宫问题
    (啊哈哈哈鸡汤来咯)设有一个N×N(2<=N<=10)方格的迷宫,入口和出口分别在左上角和右上角。迷宫格子中分别放0和1,0表示可通,1表示不能,入口和出口处肯定是0.迷宫走的规则如下所......
  • dfs入门,一个简单的迷宫问题
    AcWing走迷宫问题给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1......
  • 迷宫危机“分支语句”
    今日份学习“分支语句”本文简介:该篇文章介绍分支语句,主要讲解其用法和注意事项,让我们使用该语句上有更好的概念(不再犯选择困难症......