题解 | #[NOIP2017]棋盘#
[NOIP2017]棋盘
https://ac.nowcoder.com/acm/problem/16423
题目大意:
(1)从地图左上角走到右下角,不能斜着走
(2)有红、黄两种颜色的格子。相邻颜色格子,同颜色不用花钱,不同颜色要花1个金币
(3)遇到无颜色(白色)格子,可用一次魔法使其有红、黄中任意一种颜色,但不能连续使用。使用一次需花2个金币
(4)求出整个过程最小费用
思路分析:
(1)有图有格子,我们想到bfs(最为经典)
(2)**最关键的一点** :这和普通的bfs不同,并不是要找第一个到达终点的路线的费用,而是要找花费最少的费用,因此在到达终点后不能直接结束程序。这涉及到要多次访问同一个点,因此用一个数组val来存储每个点的最小花费,故称之为“记忆化搜索”。(上面的dalao也讲述过,本弱鸡只做通俗解释)
(3)bfs队列存储元素:x,y坐标、当前格子最小值、当前格子颜色。注意,由于可能出现多次访问某些点的情况,假若其中一些点无色,便会弄乱地图。因此我们要将每一步颜色存入对应的在队列中的位置,然后用原本的输入数组map记录原始的颜色
(4)bfs的判断条件:
大条件:没有越界。
1.当访问到的格子有颜色:
跟新本点最小花费:是否更优解为上个点最小花费(val[beforex][beforey])加上每格花费
val[nowx][nowy]=min(val[nowx][nowy], val[beforex][beforey]+abs(map[nowx][nowy]-map[beforex][beforey]))
再存入队列即可
2.当访问到的格子无颜色:
若上个格子无颜色,则不成立(通过查看原始图map)
否则:更新本点最小花费,类似于上面的
val[nowx][nowy]=min(val[nowx][nowy],val[beforex][beforey]+2)
再存入队列。注意存入颜色为上一个格子的颜色,因为这是贪心最优解(想想为什么)
易错指南:
本题用动态规划更新每个点很麻烦,因为本题在图上行走的方向可以是4个,而动态规划的一般适用于2个方向。
满分代码:
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
const int INF = 0x7ffffff;
const int N = 105;
struct T {
int xp, yp, v, c;
//x,y坐标,价格,颜色
};
int m, n, x, y, c;
int a[N][N], val[N][N], ans = -1;
// a数组存储原图,相当于前面说明的map
// val存储最小花费
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue<T> Q;
void bfs() {
val[1][1] = 0;
Q.push(T{1, 1, 0, a[1][1]});
while (!Q.empty()) {
T head = Q.front();
Q.pop();
int bx = head.xp, by = head.yp;
int bv = head.v, bc = head.c;
// 上一个访问点的x,y坐标、最小花费和颜色
for (int i = 0; i < 4; i++) {
int cx = bx + dx[i];
int cy = by + dy[i];
// cx,cy为目前站在的点的x,y坐标
if (cx > 0 && cy > 0 && cy <= m && cy <= m) {// 是否越界
if (a[cx][cy]){
if (val[cx][cy] > bv + abs(bc - a[cx][cy])) {// 更新最小花费
val[cx][cy] = bv + abs(bc - a[cx][cy]);
Q.push(T{cx, cy, val[cx][cy], a[cx][cy]});
}
}
else {
if (!a[bx][by]) continue ;
if (val[cx][cy] > bv + 2) {// 同上
val[cx][cy] = bv + 2;
Q.push(T{cx, cy, val[cx][cy], bc});
}
}
}
}
}
if (val[m][m] != INF) ans = val[m][m];
// 若能够到达终点
return ;
}
int main() {
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d %d", &x, &y, &c);
a[x][y] = c + 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
val[i][j] = INF;
}
}
bfs();
printf("%d", ans);
}
写在最后:
这篇题解是本弱鸡写的第一篇题解,望各位大佬帮忙指点指点,同时也希望大家多多鼓励,谢谢!