题解 P3956 【棋盘】

beretty · 2017-12-15 17:01:02 · 题解

//棋盘。。
//我可能是个zz
//打这个题打了1下午。。。。。
//上来先瞎jb搜了一波，搜了65。。。（还WA了几个点。。。。）然后就灰溜溜的换用DP。。
//以上都是废话
//好吧，可能往下也是废话。。。
//看到没人用DP（好吧，楼下就是，我眼瞎）
//那至少没人用四维的对吧。。。（不过能用二维我闲的蛋疼非要用四维）
//f[i][j][k][l]表示到（i,j）点颜色为k时的最小金币花费数。。。然后那个l就是上一次用没用魔法
//通过四个方向更新
//然后想必各位dalao就知道DP该怎么整了
//哦，对了，还有个坑点，就是要在DP时循环4遍，因为可能有好几个方向能更新f（就这个坑点就让我在95卡了好久。。。）
//然后放下代码吧。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M = 205;
const int inf = 210000000 ;
int w[M][M];
int m,n,x,y,z;
int ans=210000000;
int f[M][M][3][2];
int main()
{
//    freopen("chess.out","w",stdout);
    int i,j,k,l;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        w[x][y]=z+1;
    }
    memset(f,127/3,sizeof(f));
    f[1][1][w[1][1]][1]=0;
    int T=4;
    while(T--)
    for(i=1;i<=m;i++)
      for(j=1;j<=m;j++)
      {
          if(i==1&&j==1) continue;
          if(w[i][j])
          {
            for(k=1;k<=2;k++)
            for(l=0;l<=1;l++)
              if(w[i][j]==k)
              {
                  int temp=f[i][j][k][1];
                  f[i][j][w[i][j]][1]=min(f[i-1][j][k][l],min(f[i][j-1][k][l],min(f[i][j+1][k][l],f[i+1][j][k][l])));
                  f[i][j][w[i][j]][1]=min(temp,f[i][j][k][1]);
              }
              else
              {
                  int temp=f[i][j][w[i][j]][1];
                  f[i][j][w[i][j]][1]=min(f[i-1][j][k][l],min(f[i][j-1][k][l],min(f[i][j+1][k][l],f[i+1][j][k][l])))+1;
                  f[i][j][w[i][j]][1]=min(temp,f[i][j][w[i][j]][1]);
              }
        }
        else
        for(int k=1;k<=2;k++)
        {
            int temp=f[i][j][k][0];
            f[i][j][k][0]=min(f[i-1][j][k][1],min(f[i][j-1][k][1],min(f[i][j+1][k][1],f[i+1][j][k][1])))+2;
            f[i][j][k][0]=min(temp,f[i][j][k][0]);
        }
      }
    ans=min(ans,min(f[m][m][1][1],min(f[m][m][1][0],min(f[m][m][2][1],f[m][m][2][0]))));
    if(ans==inf)
    printf("-1\n");
    else
    printf("%d\n",ans);
    return 0;
}