每日热文：洛谷P3956. [NOIP2017. PJ]棋盘

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

每日热文：洛谷P3956. [NOIP2017. PJ]棋盘

2023-01-10 06:10:35 来源：博客园

题目简述

$\qquad$走在一个棋盘上，棋盘上染着颜色，有三种颜色：红、黄、无，当你从一个格子走向另一个格子时，同色格子不花费，异色格子花费$1$，无色格子不能走，但是可以用魔法将其染成当前所处格子的颜色，花费$2$。求$(1,1)$到$(m,m)$的最短路。

(资料图片仅供参考)

解题思路

$\qquad$因为这个数据范围非常小，是$1\le m\le 100$，代表我们棋盘上至多有$10000$个格子，所以我们就有了一个爆搜的思路：：问题来了，如何dfs求解？

状态表示：

$\qquad$我们首先分析一下状态转移的时候必须要考虑的因素：$\qquad 1.$首先当然是状态点的坐标$(x,y)$，这个不存就不能做到正确的转移，会到别的点。$\qquad 2.$其次是花费，因为每个点到其他点的花费按照规则有一定的区别，所以也要存下花费$\qquad 3.$然后就是有没有用过魔法，因为有不能用连续的两次魔法，所以如果这个点是用过魔法的，那转移过去的时候就不能也用魔法$\qquad$$\qquad$

这样一通分析下来，我们$DFS$需要的参数差不多就出来了

\[dfs(x,y,cost,used)\]

状态转移

$\qquad$总感觉这写着像$DP$，但是又找不到别的词来形容，所以只能这样了$()$

$\qquad$首先我们继续进行分类：对于每个由$(x,y)$转移过来的节点$(nx,ny)$，我们进行如下讨论：

$\qquad\quad 1.$当超出棋盘时，不能转移，做可行性剪枝。$\qquad\quad 2.$当$(nx,ny)$无色时，再分两类：

$\qquad\qquad a.$如果在$(x,y)$点已经用过魔法，那么由于不能连续使用，不可转移

$\qquad\qquad b.$如果在$(x,y)$点没有用过魔法，那么可以使用魔法染色，花费$2$。

$\qquad\quad 3.$当$(nx,ny)$与$(x,y)$不同色时：转移，花费$1$$\qquad\quad 4.$否则转移，花费$2$

总结起来就是$$1不可转移$$

\[2.a\ dfs(x,y,cost,1) \to 无法转移，用过魔法\]\[2.b\ dfs(x,y,cost,0)\to dfs(nx,ny,cost+2,1)\]\[3.dfs(x,y,cost,used)\to dfs(nx,ny,cost+1,0)\]\[4.dfs(x,y,cost,used)\to dfs(nx,ny,cost,0)\]

剪枝

$\qquad$这题不剪枝是过不了的，会爆栈。$\qquad$所以我们可以加一个很简单的剪枝，当走到某个点的花费已经比目前最优解贵了，就不搜了，因为无论如何都不能更好，没有搜索的价值。

代码

#include #include #include using namespace std;const int N = 110, INF = 0x3f3f3f3f;int g[N][N], n, m, dist[N][N];int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};void dfs(int x, int y, int cost, int used) {    if (dist[x][y] <= cost) return ;        dist[x][y] = cost;        if (x == m && y == m) return ;        for (int i = 0; i < 4; i ++ )     {        int nx = x + dx[i], ny = dy[i] + y;        if (nx < 1 || nx > m || ny < 1 || ny > m) continue ;                if (g[nx][ny] == -1)         {            if (used) continue ;            else {                g[nx][ny] = g[x][y];                dfs(nx, ny, cost + 2, 1);                g[nx][ny] = -1;            }        }        else if (g[nx][ny] == g[x][y]) dfs(nx, ny, cost, 0);        else dfs(nx, ny, cost + 1, 0);    }}int main() {    scanf("%d%d", &m, &n);        memset(g, -1, sizeof g);    while (n -- )     {        int a, b, c;        scanf("%d%d%d", &a, &b, &c);        g[a][b] = c;    }    memset(dist, 0x3f, sizeof dist);        dfs(1, 1, 0, 0);    if (dist[m][m] == INF) puts("-1");    else printf("%d\n", dist[m][m]);        return 0;}

关键词：可以使用无论如何只能这样了