洛谷P3956. [NOIP2017. PJ]棋盘

题目简述

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

解题思路

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

状态表示：

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

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

状态转移

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

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

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

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

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

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

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

剪枝

(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
", dist[m][m]);
    
    return 0;
}