题目简述
$\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 <iostream>
#include <cstring>
#include <algorithm>
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;
}