备战蓝桥杯---搜索(进阶2)

news/2024/4/23 3:09:22

话不多说,直接看题:

相当于找一个点使它到3个国家的距离和min,显然,我们不可以枚举点,但是,我们可以对这3个国家分别bfs,然后枚举相加即可。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,v1[1005][1005],v2[1005][1005],v3[1005][1005],mm,mmm,x1,yr,x2,y2,x3,y3,min1=10000000;
char a[1005][1005],q; 
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node{int x,y,t;
};
deque<node> qq;
void bfs(int num,int v[][1005],int x,int y){while(!qq.empty()) qq.pop_front();qq.push_back({x,y,0});while(!qq.empty()){node ss=qq.front();qq.pop_front();if(v[ss.x][ss.y]!=-1) continue;v[ss.x][ss.y]=ss.t;for(int i=0;i<4;i++){int xx=ss.x+dir[i][0];int yy=ss.y+dir[i][1];if(xx<=0||xx>n||yy<=0||yy>m) continue;if(a[xx][yy]=='#') continue;if(v[xx][yy]!=-1) continue;if((a[xx][yy]-'0'>=1)&&(a[xx][yy]-'0'<=3)) qq.push_front({xx,yy,ss.t});else qq.push_back({xx,yy,ss.t+1});}}
}
signed main(){memset(v1,-1,sizeof(v1));memset(v2,-1,sizeof(v2));memset(v3,-1,sizeof(v3));cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>q;if(q=='1'){x1=i;yr=j;}if(q=='2'){x2=i;y2=j;}if(q=='3'){x3=i;y3=j;}a[i][j]=q;}}bfs(1,v1,x1,yr);bfs(2,v2,x2,y2);bfs(3,v3,x3,y3);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(v1[i][j]==-1||v2[i][j]==-1||v3[i][j]==-1) continue;if(a[i][j]=='#') continue;if(a[i][j]=='.'&&min1>v1[i][j]+v2[i][j]+v3[i][j]-2)min1=v1[i][j]+v2[i][j]+v3[i][j]-2;if(a[i][j]!='#'&&min1>v1[i][j]+v2[i][j]+v3[i][j])min1=v1[i][j]+v2[i][j]+v3[i][j];}}if(min1==10000000) cout<<-1;else cout<<min1;}

有几点主意:

1.合并时分类讨论

2.可能存在2,3已经联通,这样的话算不在123位置上的结果就重复了导致结果偏大。

但是总有一个正确的结果可以获得,与是没有必要判断。

接题:

显然,我们最多可以通过abs(n-m)次转化,然后当数大于2*n-m就退出。

其实,负数的存在是没必要的;

于是我们可以BFS,复杂度不超过n-m;

class Solution {
public:int solve(int n, int m) {int vis[3001];struct node{int f,cnt;};queue<node> q;q.push({n,0});vis[n]=1;memset(vis,0,sizeof(vis));while(!q.empty()){node ss=q.front();q.pop();if(ss.f==m){return ss.cnt;}if(ss.cnt>abs(n-m)) continue;int xx=ss.f;for(int i=1;i<=3;i++){xx=ss.f;if(i==1) xx++;else if(i==2) xx--;else xx=xx*xx;if(xx<=0) continue;if(xx>m&&(ss.cnt+xx-m)>=abs(m-n)) continue;if(vis[xx]==1) continue;q.push({xx,ss.cnt+1});vis[xx]=1; }}return -1;}
};

接题:

二进制枚举+检验即可,复杂度为(2^n*m)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.cpky.cn/p/8035.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

力扣hot100 -- 双指针

目录 &#x1f382;移动零 &#x1f319;盛最多水的容器 &#x1f33c;三数之和 &#x1f33c;接雨水 前缀和 辅助数组 双指针 单调栈 &#x1f382;移动零 283. 移动零 - 力扣&#xff08;LeetCode&#xff09; 关于swap #include <iostream> #include <vec…

Flink cdc3.0动态变更表结构——源码解析

文章目录 前言源码解析1. 接收schema变更事件2. 发起schema变更请求3. schema变更请求具体处理4. 广播刷新事件并阻塞5. 处理FlushEvent6. 修改sink端schema 结尾 前言 上一篇Flink cdc3.0同步实例 介绍了最新的一些功能和问题&#xff0c;本篇来看下新功能之一的动态变更表结…

智慧自助餐饮系统(SpringBoot+MP+Vue+微信小程序+JNI+ncnn+YOLOX-Nano)

一、项目简介 本项目是配合智慧自助餐厅下的一套综合系统&#xff0c;该系统分为安卓端、微信小程序用户端以及后台管理系统。安卓端利用图像识别技术进行识别多种不同菜品&#xff0c;识别成功后安卓端显示该订单菜品以及价格并且生成进入小程序的二维码&#xff0c;用户扫描…

WPF中值转换器的使用

什么是值转换器 在WPF&#xff08;Windows Presentation Foundation&#xff09;中&#xff0c;值转换器&#xff08;Value Converter&#xff09;是一种机制&#xff0c;允许你在绑定时转换绑定源和绑定目标之间的值。值转换器实现了 IValueConverter 接口&#xff0c;该接口…

简单的TcpServer(英译中)

目录 一、TCP socket API 详解1.1 socket()1.2 bind()1.3 listen()1.4 accept()1.5 connect 二、TcpServer&#xff08;英译中&#xff09;2.1 TcpServer.hpp2.2 TcpClient.cc2.3 Task.hpp2.4 Thread.hpp2.5 ThreadPool.hpp2.6 makefile2.7 Main.cc2.8 log.hpp2.9 Init.hpp2.10…

分享3款开源免费好用的Docker可视化管理工具安装部署教程

文章目录 1.前言2.Docker Desktop3.Portainer3.1 Portainer默认英文版本安装3.2 Portainer汉化版本安装3.3官方镜像说明3.3.1ssl访问3.3.2Nginx反代3.3.3Nginx反代设置子目录3.3.4docker-compose部署 3.4登录 4.DockerUI4.1简介4.2项目地址4.3部署启动命令4.4登录4.5首页 5.总结…