Summary

洛谷 P3956 棋盘 的题解,
算法为 DFS .

Link

题目链接

Text

时隔 (接近) 一年再来解决当初的题

这道题我在考场上想到了 DFS, 然后又想到了一个很小的剪枝, 于是拿了 90 分

后来改了一点点, 就 A 了. 不知道怎么回事,可能是玄学??

就是把这一段

c[x][y]=z+1;
f[x][y]=true;

改成了

c[y][x]=z+1;
f[y][x]=true;

这一段

其中膜法改变颜色时需要想想改成什么颜色. 直觉是改成和当前一样就好了, 这里给出 并不严谨的 证明:

用 H 代表红色,Y 代表黄色, 则
当 H ->?->H 时,? 为 H 代价为 2,Y 代价为 4;
当 H ->?->Y 时,? 为 H 和 Y 代价都为 3.

所以改成和当前一样就是最节省代价的做法

Code

money 数组是走到某个点的已知最小代价,c 是颜色,f 是有无颜色

#include <stdio.h>

int m,n,money[105][105],c[105][105];
bool f[105][105];

void dfs(int x,int y,int now)//now是当前代价
{
    if (now>=money[x][y]) return;//剪枝 一旦当前代价大于之前的最小代价就不用搜了
    money[x][y]=now;
    if (f[x][y])//如果当前点有颜色
    {
        if (f[x-1][y])//如果目标点也有颜色
        {
            if (c[x-1][y]==c[x][y]) dfs(x-1,y,now);//颜色一样 代价不变
            else dfs(x-1,y,now+1);//颜色不一样 代价加一
        }
        else//目标点没有颜色 因为这一步有颜色 所以可以用膜法
        {
            c[x-1][y]=c[x][y];//改变颜色
            dfs(x-1,y,now+2);
            c[x-1][y]=0;//改回来
        }
        if (f[x+1][y])//同上 搜另一个点
        {
            if (c[x+1][y]==c[x][y]) dfs(x+1,y,now);
            else dfs(x+1,y,now+1);
        }
        else
        {
            c[x+1][y]=c[x][y];
            dfs(x+1,y,now+2);
            c[x+1][y]=0;
        }
        if (f[x][y-1])//同上 搜另一个点
        {
            if (c[x][y-1]==c[x][y]) dfs(x,y-1,now);
            else dfs(x,y-1,now+1);
        }
        else
        {
            c[x][y-1]=c[x][y];
            dfs(x,y-1,now+2);
            c[x][y-1]=0;
        }
        if (f[x][y+1])//同上 搜另一个点
        {
            if (c[x][y+1]==c[x][y]) dfs(x,y+1,now);
            else dfs(x,y+1,now+1);
        }
        else
        {
            c[x][y+1]=c[x][y];
            dfs(x,y+1,now+2);
            c[x][y+1]=0;
        }
    }
    else//如果当前点没有颜色 就不能使用膜法
    {
        if (f[x-1][y])//只有目标点有颜色才能搜
        {
            if (c[x-1][y]==c[x][y]) dfs(x-1,y,now);
            else dfs(x-1,y,now+1);
        }
        if (f[x+1][y])//同上 搜另一个点
        {
            if (c[x+1][y]==c[x][y]) dfs(x+1,y,now);
            else dfs(x+1,y,now+1);
        }
        if (f[x][y-1])//同上 搜另一个点
        {
            if (c[x][y-1]==c[x][y]) dfs(x,y-1,now);
            else dfs(x,y-1,now+1);
        }
        if (f[x][y+1])//同上 搜另一个点
        {
            if (c[x][y+1]==c[x][y]) dfs(x,y+1,now);
            else dfs(x,y+1,now+1);
        }
    }
}

int main()
{
    for (int i=0;i<105;i++)
    {
        for (int j=0;j<105;j++) money[i][j]=100000000;
    }
    scanf ("%d%d",&m,&n);
    for (int i=1;i<=n;i++)
    {
        int x,y,z;
        scanf ("%d%d%d",&x,&y,&z);
        /*
        c[x][y]=z+1;
        f[x][y]=true;
        我考场上用了这一段,就莫名少了10分
        */
        c[y][x]=z+1;
        f[y][x]=true;
    }//读入
    dfs(1,1,0);//搜索
    if (money[m][m]==100000000) printf ("-1");//特判
    else printf ("%d",money[m][m]);//输出
    return 0;
}