题解 P3956 【棋盘】

· · 题解

虽然不敢称自己dalao，但是其他题解的DP好像都是错的诶qaq…… 因为DP的递推方向是从左上往右下推的，无法考虑从右边或者下边走到当前位置的情况，所以只进行一次DP并不一定会得到最优解。那么，进行第二次DP的时候，右边和下边的点已经是被更新过的了，因此第二次DP就会考虑到向左走一次或者向上走一次的情况了。以此类推，只要进行m次DP就可以把所有的情况都考虑到了。 代码有点恶心，虽然有很多转移是可以不用写的，但是为了整齐还是写上了qwq

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
using namespace std;
int n,m;
int map[105][105];
int f[105][105][3][3];//i,j坐标,k当前格子颜色，l=1到当前点用魔法，l=0到当前点没用魔法 

int main()
{
    memset(map,-1,sizeof(map));
    memset(f,63,sizeof(f));
    scanf("%d%d",&m,&n);
    int maxx=f[m][m][0][0];
    int x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        scanf("%d",&map[x][y]);
    }   
    f[1][1][map[1][1]][0]=0;
    for(int k=1;k<=m;k++)
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
    {
        if(map[i][j]==1)//当前点是黄色 
        {
            f[i][j][1][0]=MIN(f[i][j][1][0],MIN(f[i-1][j][1][0],MIN(f[i-1][j][1][1],MIN(f[i-1][j][0][0]+1,f[i-1][j][0][1]+3))));
            f[i][j][1][0]=MIN(f[i][j][1][0],MIN(f[i][j-1][1][0],MIN(f[i][j-1][1][1],MIN(f[i][j-1][0][0]+1,f[i][j-1][0][1]+3))));
            f[i][j][1][0]=MIN(f[i][j][1][0],MIN(f[i+1][j][1][0],MIN(f[i+1][j][1][1],MIN(f[i+1][j][0][0]+1,f[i+1][j][0][1]+3))));
            f[i][j][1][0]=MIN(f[i][j][1][0],MIN(f[i][j+1][1][0],MIN(f[i][j+1][1][1],MIN(f[i][j+1][0][0]+1,f[i][j+1][0][1]+3))));
        }
        if(map[i][j]==0)//rednow
        {
            f[i][j][0][0]=MIN(f[i][j][0][0],MIN(f[i-1][j][0][0],MIN(f[i-1][j][0][1],MIN(f[i-1][j][1][0]+1,f[i-1][j][1][1]+3))));
            f[i][j][0][0]=MIN(f[i][j][0][0],MIN(f[i][j-1][0][0],MIN(f[i][j-1][0][1],MIN(f[i][j-1][1][0]+1,f[i][j-1][1][1]+3))));
            f[i][j][0][0]=MIN(f[i][j][0][0],MIN(f[i+1][j][0][0],MIN(f[i+1][j][0][1],MIN(f[i+1][j][1][0]+1,f[i+1][j][1][1]+3))));
            f[i][j][0][0]=MIN(f[i][j][0][0],MIN(f[i][j+1][0][0],MIN(f[i][j+1][0][1],MIN(f[i][j+1][1][0]+1,f[i][j+1][1][1]+3))));
        }
        else //whitenow
        {
            f[i][j][1][1]=MIN(f[i][j][1][1],MIN(f[i][j][1][0]+2,MIN(f[i-1][j][1][0]+2,f[i-1][j][0][0]+3)));
            f[i][j][1][1]=MIN(f[i][j][1][1],MIN(f[i][j][1][0]+2,MIN(f[i][j-1][1][0]+2,f[i][j-1][0][0]+3)));
            f[i][j][1][1]=MIN(f[i][j][1][1],MIN(f[i][j][1][0]+2,MIN(f[i+1][j][1][0]+2,f[i+1][j][0][0]+3)));
            f[i][j][1][1]=MIN(f[i][j][1][1],MIN(f[i][j][1][0]+2,MIN(f[i][j+1][1][0]+2,f[i][j+1][0][0]+3)));
            f[i][j][0][1]=MIN(f[i][j][0][1],MIN(f[i][j][0][0]+2,MIN(f[i-1][j][0][0]+2,f[i-1][j][1][0]+3)));
            f[i][j][0][1]=MIN(f[i][j][0][1],MIN(f[i][j][0][0]+2,MIN(f[i][j-1][0][0]+2,f[i][j-1][1][0]+3)));
            f[i][j][0][1]=MIN(f[i][j][0][1],MIN(f[i][j][0][0]+2,MIN(f[i+1][j][0][0]+2,f[i+1][j][1][0]+3)));
            f[i][j][0][1]=MIN(f[i][j][0][1],MIN(f[i][j][0][0]+2,MIN(f[i][j+1][0][0]+2,f[i][j+1][1][0]+3)));
        }
    }
    int min=MIN(f[m][m][0][1],MIN(f[m][m][0][0],MIN(f[m][m][1][0],f[m][m][1][1])));
    if(min==maxx)min=-1;printf("%d",min);
}