题解：P3956 [NOIP2017 普及组] 棋盘

Mountains_OIer · 2025-01-05 08:55:25 · 题解

思路

这道题我们考虑搜索，有三种情况：

1. 下一个格子颜色相同，无需花费金币。
2. 下一个格子颜色不同，需要花费 1 个金币。
3. 下一个格子无色，需要施用魔法，将下一个格子变为指定的颜色，需要花费 2 个金币。

如果施用了魔法，那么需要注意几个特殊的情况：

• 魔法的时间很短暂，当你离开被施魔法的格子时，要将格子颜色恢复为无色。
• 魔法不能连续施用，所以搜索时，我们还需要判断上一步是否施用了魔法。

CODE

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],f[1005][1005],m,n,x,y,c;
void dfs(int i,int j,int c,bool flag,int w){
    if(i>m||i<1||j<1||j>m)return;
    f[i][j]=w;
    if(w+abs(c-a[i-1][j])<f[i-1][j]&&a[i-1][j]!=-1)dfs(i-1,j,a[i-1][j],1,w+abs(c-a[i-1][j]));
    if(w+abs(c-a[i][j-1])<f[i][j-1]&&a[i][j-1]!=-1)dfs(i,j-1,a[i][j-1],1,w+abs(c-a[i][j-1]));
    if(w+abs(c-a[i+1][j])<f[i+1][j]&&a[i+1][j]!=-1)dfs(i+1,j,a[i+1][j],1,w+abs(c-a[i+1][j]));
    if(w+abs(c-a[i][j+1])<f[i][j+1]&&a[i][j+1]!=-1)dfs(i,j+1,a[i][j+1],1,w+abs(c-a[i][j+1]));
    if(flag==1){// 上一步施用了魔法
        if(w+2<f[i-1][j]&&a[i-1][j]==-1)dfs(i-1,j,c,0,w+2);
        if(w+2<f[i][j-1]&&a[i][j-1]==-1)dfs(i,j-1,c,0,w+2);
        if(w+2<f[i+1][j]&&a[i+1][j]==-1)dfs(i+1,j,c,0,w+2);
        if(w+2<f[i][j+1]&&a[i][j+1]==-1)dfs(i,j+1,c,0,w+2);
    }
    return;
}
signed main(){
    memset(a,-1,sizeof(a));
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>c;
        a[x][y]=c;
    }
    memset(f,127,sizeof(f));
    int s=f[m][m];
    dfs(1,1,a[1][1],1,0);
    if(f[m][m]==s)f[m][m]=-1;//无解 
    cout<<f[m][m];
}