今日学习记录
1. P3956 [NOIP 2017 普及组] 棋盘 - 洛谷
关键词：bfs 优先队列
问题分析：
从左上角走到右下角,其中格子中有不同的颜色
核心思路: 首先先想到的是最短路径问题,但是先回答一个问题,最短的那条路一定花费金币最少吗? 如果有一条路很长,但是都是相同颜色,无疑消耗最少 可是这样一来使用常规的 bfs 也要搜索所有的路径进行比较,与 dfs 无啥区别,但是我们的眼界不一定要局限于路径,我们要找到的是花费钱最少的路径,我们主要沿着钱少的路径搜索
贪心(优先队列)
我们要最后钱花费最少,当我位于地图中的任何一点的时候,我任何选择,是不是要选择当前对于我来说花费钱最少的那条路径,我们使用优先队列实现,每次优先搜索钱少的路
bfs
在记录数组状态的时候,发现相同的位置,在上一个点状态不同的时候,对下一个点的影响不同,所以要记录每次的颜色不同状态,于是我们的点位信息为(a,b,c,w),(a,b)为坐标,c为当前格子颜色,w 为钱,就是常规的 bfs 遍历,就是分类讨论
首先要记忆化搜索,要记录颜色状态,其他都一样
- 都为空直接跳过
- 当前不为空,下一个为空,施展变色魔法!下一个位置的颜色状态以当前颜色为准,同时累加 2
- 当前为空,下一个不为空,由于原数组的颜色记录和我们创建的结构体中的颜色是单独的,所以可以区别,先判断在原数组中当前为空,下一个不为空,再看记录中的颜色状态,与下一个颜色比较
- 相同的颜色,直接下一个
- 不同的颜色,累加 1
**最终代码：
#include <bits/stdc++.h>
using namespace std;
int m,n;
const int DIR[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct node{
int a,b,c,w;
bool operator < (node other)const{
return w>other.w;
}
};
priority_queue<node> q;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>m>>n;
vector arr(m+1,vector<int>(m+1,3));
while(n--){
int x,y,p;cin>>x>>y>>p;
arr[x][y] = p;
}
vector vis(m+1,vector(m+1,vector<bool>(4)));
q.push((node){1,1,arr[1][1],0});
vis[1][1][arr[1][1]] = true;
int ans = INT_MAX;
while(!q.empty()){
int size = q.size();
for(int i= 0;i<size;i++){
auto cur = q.top();q.pop();
if(cur.a==m&&cur.b==m){
ans = cur.w;
goto br;
}
int cr = arr[cur.a][cur.b];
for(auto &d:DIR){
int x = cur.a+d[0],y = cur.b+d[1];
int z = arr[x][y],sum = cur.w;
if(x>0&&x<=m&&y>0&&y<=m&&!vis[x][y][z]){
//判断颜色的时候要保证都不为空
//要优先判断空的情况,空的情况分为三种
//都为空
if(cr==3&&z==3) continue;
//当前不为空,下一个为空,施展变色魔法!
else if(cr!=3&&z==3) q.push({x,y,cr,sum+=2}),vis[x][y][cr] = true;
//当前为空,下一个不为空
else if(cr==3&&z!=3){
if(cur.c==z) q.push({x,y,z,sum}),vis[x][y][z] = true;
else q.push({x,y,z,sum+1}),vis[x][y][z] = true;
}
//相同的颜色
else if(z==cr) q.push({x,y,z,sum}),vis[x][y][z] = true;
//不同的颜色
if(z!=cr) q.push({x,y,z,sum+1}),vis[x][y][z] = true;
}
}
}
}
br:;
if(ans!=INT_MAX) cout<<ans;
else cout<<-1;
return 0;
}学到的点：
- 优先队列+bfs