P3956 棋盘

题目描述

有一个\(m×m\)的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。

任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费1个金币。

另外，你可以花费2个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用，而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。

现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？

输入输出格式

输入格式：

第一行包含两个正整数\(m,n\) ，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。

接下来的\(n\)行，每行三个正整数\(x, y, c\)，分别表示坐标为\((x,y)\)的格子有颜色\(c\)。

其中\(c=1\)代表黄色，\(c=0\)代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标为(1,1) ，右下角的坐标为\((m,m)\) 。

棋盘上其余的格子都是无色。保证棋盘的左上角，也就是(1,1) 一定是有颜色的。

输出格式：

一个整数，表示花费的金币的最小值，如果无法到达，输出-1 。

数据规模与约定

对于 30% 的数据, 1≤m≤5,1≤n≤10 。

对于 60% 的数据, 1≤m≤20,1≤n≤200 。

对于 100% 的数据, 1≤m≤100,1≤n≤1,000 。

这道题让我收获巨大。

首先，先入为主的，我想到了DP，初始态为左上角，终态为右下角，每个状态由它的左边和上面的点转移。

因为是否用了魔法也算作状态，所以DP方程设计的比较繁琐

令\(dp[i][j][k][l]\)代表\(i\)行\(j\)列颜色为\(k(1/0)\)是否使用魔法(\(l\)为0为没有使用)

转移直接看代码就行

code:

#include <cstdio>

#include <cstring>

int min(int x,int y){return x<y?x:y;}

const int M=105;

int g[M][M],dp[M][M][2][2],m,n;

int main()

{

    scanf("%d%d",&m,&n);

    int x,y,c;

    memset(g,-1,sizeof(g));

    memset(dp,0x3f,sizeof(dp));

    for(int i=1;i<=n;i++)

    {

        scanf("%d%d%d",&x,&y,&c);

        g[x][y]=c;

    }

    dp[0][1][0][0]=dp[0][1][1][0]=0;

    for(int i=1;i<=m;i++)

        for(int j=1;j<=m;j++)

        {

            int col=g[i][j];

            if(col!=-1)

            {

                dp[i][j][col][0]=min(min(dp[i-1][j][col][0],dp[i-1][j][col][1]),dp[i][j][col][0]);

                dp[i][j][col][0]=min(min(dp[i-1][j][col^1][0],dp[i-1][j][col^1][1])+1,dp[i][j][col][0]);

                dp[i][j][col][0]=min(min(dp[i][j-1][col][0],dp[i][j-1][col][1]),dp[i][j][col][0]);

                dp[i][j][col][0]=min(min(dp[i][j-1][col^1][0],dp[i][j-1][col^1][1])+1,dp[i][j][col][0]);

            }

            else

            {

                dp[i][j][1][1]=min(min(dp[i-1][j][1][0],dp[i-1][j][0][0]+1),min(dp[i][j-1][1][0],dp[i][j-1][0][0]+1))+2;

                dp[i][j][0][1]=min(min(dp[i-1][j][0][0],dp[i-1][j][1][0]+1),min(dp[i][j-1][0][0],dp[i][j-1][1][0]+1))+2;

            }

        }

    int ans=min(min(dp[m][m][1][1],dp[m][m][1][0]),min(dp[m][m][0][1],dp[m][m][0][0]));

    if(ans==0x3f3f3f3f)

        printf("-1\n");

    else

        printf("%d\n",ans);

    return 0;

}

然而

最开始我以为是方程的某些细节错了（毕竟转移方程好麻烦啊），后来翻了洛谷上的一些题解才明白可以从右边或下面转。

那么状态转移方程似乎就不好设计了，因为不知道要先做谁啊。

翻了一下题解，大多是一些记搜或是搜索剪枝，但一个最短路建模吸引了我的注意。

于是\(Dijk\)的贪心思想出来了。

用二叉堆维护，每次取出答案最小的点去更新其他的点，则一定是正确的（图中无负边）

具体地，维护一个五元组\((x,y,col,is,w)\)，分别代表坐标，颜色，是否用膜法，当前答案，每次朝四个方向更新即可。

从我的理解来看，这道题把我对 Dijk，动态规划和广搜的理解放在了一起，让我感觉到它们有着本质上的相似，只是在基础上又加上了一些限制而已。

广搜：不管是否优秀都进行暴力的枚举

动态规划：基于Dijk的贪心使方程有了无后效性

Dijk：贪心的思想其实也基于了一种动态规划

欢迎大家提出不足之处！

code:

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int M=105;

const int X[5]={0,0,1,0,-1};

const int Y[5]={0,1,0,-1,0};

int g[M][M],m,n,used[M][M][2][2];

struct node

{

    int x,y,col,is,w;

    bool friend operator <(node n1,node n2)

    {

        return n1.w>n2.w;

    }

    node(){}

    node(int x,int y,int col,int is,int w)

    {

        this->x=x;this->y=y;this->col=col;

        this->is=is;this->w=w;

    }

};

priority_queue <node > q;

int main()

{

    scanf("%d%d",&m,&n);

    int x0,y0,c;

    memset(g,-1,sizeof(g));

    for(int i=1;i<=n;i++)

    {

        scanf("%d%d%d",&x0,&y0,&c);

        g[x0][y0]=c;

    }

    node t0(1,1,g[1][1],0,0);

    q.push(t0);

    int ans=0x3f3f3f3f;

    while(!q.empty())

    {

        node from=q.top();

        q.pop();

        int x=from.x,y=from.y,col=from.col,is=from.is,w=from.w;

        if(used[x][y][col][is]) continue;

        if(x==m&&y==m) {ans=w;break;}

        used[x][y][col][is]=1;

        for(int i=1;i<=4;i++)

        {

            int xx=X[i]+x,yy=Y[i]+y;

            if(xx==0||xx==m+1||yy==0||yy==m+1) continue;

            if(g[xx][yy]!=-1)

            {

                if(!used[xx][yy][g[xx][yy]][0])

                {

                    node tt(xx,yy,g[xx][yy],0,w+(col^g[xx][yy]));

                    q.push(tt);

                }

            }

            else if(!is)

            {

                if(!used[xx][yy][col][1])

                {

                    node tt(xx,yy,col,1,w+2);

                    q.push(tt);

                }

            }

        }

    }

    if(ans==0x3f3f3f3f)

        printf("-1\n");

    else

        printf("%d\n",ans);

    return 0;

}

巴特西

洛谷 P3956 棋盘解题报告

P3956 棋盘

题目描述

输入输出格式

输入格式：

输出格式：

数据规模与约定

最新文章

热门文章

巴特西

洛谷 P3956 棋盘 解题报告

P3956 棋盘

题目描述

输入输出格式

输入格式：

输出格式：

数据规模与约定

最新文章

热门文章

洛谷 P3956 棋盘解题报告