CSP历年复赛题-P3956 [NOIP2017 普及组] 棋盘

原题链接：https://www.luogu.com.cn/problem/P3956

题意解读：计算从(1,1)走到(m,m)的最小花费，有几个限定：

同色格子可以走，花费为0；

不同色格子可以走，花费为1；

有色格子可以走到无色格子，花费为2，且用将无色格子临时染色；

无色格子不能走到无色格子。

解题思路：

可以采用DFS来暴搜所有路径，需要四个状态：

x：横坐标

y：纵坐标

sum：花费的总金币

use：走到(x,y)是否使用了魔法

从起点开始，枚举上下左右四个位置，判断是否能走：

1、超出范围，不能走

2、已经走过，不能走

3、上一步使用了魔法，下一步位置无色，不能走

4、上一步没有使用魔法，下一步位置无色，可以使用魔法，标记成跟上一步一样的颜色

5、下一步位置有色，根据上一步的颜色计算花费

注意：对于黄色设置为1，红色设置为0，无色设置为-1

55分代码：

#include <bits/stdc++.h>
using namespace std;

const int M = 105;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int m, n;
int a[M][M];
bool vis[M][M]; //标记是否已走过
int x, y, c;
int ans = INT_MAX;

//sum：花费的金币  use：是否使用魔法
void dfs(int x, int y, int sum, bool use)
{
    if(x == m && y == m)
    {
        ans = min(ans, sum);
        return;
    }
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || nx > m || ny < 1 || ny > m || vis[nx][ny]) continue;
        if(a[nx][ny] == -1 && use) continue; //上一步是使用魔法到的且下一步无颜色

        vis[nx][ny] = true;
        if(a[nx][ny] == -1) //下一步无颜色，可以使用魔法
        {
            a[nx][ny] = a[x][y]; //用魔法变颜色,变成和上一步相同的颜色最好
            dfs(nx, ny, sum + 2, true); //使用魔法走到nx，ny
            a[nx][ny] = -1; //恢复
        }
        else //下一步有颜色
        {
            if(a[x][y] == a[nx][ny]) dfs(nx, ny, sum, false); //与上一步颜色相同
            else dfs(nx, ny, sum + 1, false); //与上一步颜色不同
        }
        vis[nx][ny] = false; //恢复
    }
}

int main()
{
    cin >> m >> n;
    memset(a, -1, sizeof(a));
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= n; i++)
    {
        cin >> x >> y >> c;
        a[x][y] = c;
    }

    vis[1][1] = true;
    dfs(1, 1, 0, false);

    if(ans == INT_MAX) cout << -1;
    else cout << ans;

    return 0;
}

由于DFS枚举的所有可能，会导致部分数据超时，需要引入剪枝方法

这里只需要一种简单的判断，当走到(x, y)时，记录下最少的花费sum，如果下一次再走到(x, y)，之前记录的花费都不超过当前的花费，则没有必要再继续DFS，可以提前结束。

只需要引入一个int f[M][M]

当f[x][y] <= sum的时候提前结束，否则就记录f[x][y] = sum

注意f[x][y]保存的是更小的sum，因此要初始化为极大值memset(f, 0x3f, sizeof(f))

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int M = 105;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int m, n;
int a[M][M];
bool vis[M][M]; //标记是否已走过
int x, y, c;
int ans = INT_MAX;
int f[M][M]; //记录走到i，j时的最小花费，初始化为极大值

//sum：花费的金币  use：是否使用魔法
void dfs(int x, int y, int sum, bool use)
{
    if(f[x][y] <= sum) return; //如果之前走过x，y，且花费更小，则不用继续了
    f[x][y] = sum; //保存更小的花费
    
    if(x == m && y == m)
    {
        ans = min(ans, sum);
        return;
    }
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || nx > m || ny < 1 || ny > m || vis[nx][ny]) continue;
        if(a[nx][ny] == -1 && use) continue; //上一步是使用魔法到的且下一步无颜色

        vis[nx][ny] = true;
        if(a[nx][ny] == -1) //下一步无颜色，可以使用魔法
        {
            a[nx][ny] = a[x][y]; //用魔法变颜色,变成和上一步相同的颜色最好
            dfs(nx, ny, sum + 2, true); //使用魔法走到nx，ny
            a[nx][ny] = -1; //恢复
        }
        else //下一步有颜色
        {
            if(a[x][y] == a[nx][ny]) dfs(nx, ny, sum, false); //与上一步颜色相同
            else dfs(nx, ny, sum + 1, false); //与上一步颜色不同
        }
        vis[nx][ny] = false; //恢复
    }
}

int main()
{
    cin >> m >> n;
    memset(a, -1, sizeof(a));
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= n; i++)
    {
        cin >> x >> y >> c;
        a[x][y] = c;
    }

    vis[1][1] = true;
    dfs(1, 1, 0, false);

    if(ans == INT_MAX) cout << -1;
    else cout << ans;

    return 0;
}