P3956 棋盘

P3956 棋盘

题解

注释都在代码里了

       这道题可以用DFS做，记忆化搜索，维护一个money[ ][ ] 表示到达当前节点的最小花费

       不需要记录VIS，因为有一个最小值判断，如果走重复的话一定会得到一个更大的花费，那就直接退出了 

代码

#include<bits/stdc++.h>

using namespace std;

int m,n;
int clor[105][105],money[105][105];
//clor是记录颜色的数组 ，0无色，1红色，2黄色
//money是记录走到(x,y)的最少花费 
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int x,y,c;
bool flag=0;  //判断有无解 

bool pan(int x,int y)
{
    return x>=1&&x<=m&&y>=1&&y<=m;
}

void dfs(int x,int y,int step,bool use)
//走到了(x,y),话费为step，use表示是否使用了魔法 
{
    if(!pan(x,y)) return;  //不合法直接退出 
    if(step>=money[x][y]) return ;
    //最小值判断
    //如果走到(x,y)的花费比之前搜到的结果还大，那么直接退出 
    money[x][y]=step;
    //更新成更小花费 
    if(x==m&&y==m)  
    {
        flag=1;
        return;
    }//有解 
    for(int i=0;i<=3;i++)  //四连通深搜 
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(pan(xx,yy))  //新节点合法 
        {
            if(clor[xx][yy]!=0) //新节点有颜色 
            {
                if(clor[xx][yy]==clor[x][y]) //新节点与原来节点同色 
                    dfs(xx,yy,step,0);

                else  //新节点与原来节点不同色 
                    dfs(xx,yy,step+1,0);
            }
            else if(!use)  //新节点无色，没有使用过魔法，可以使用魔法 
            {
                clor[xx][yy]=clor[x][y]; //暂时变色 
                dfs(xx,yy,step+2,1);
                clor[xx][yy]=0;  //回溯 
            }
        }
    }
    
}

int main()
{
    scanf("%d%d",&m,&n);
    memset(money,0x3f,sizeof(money));  //初始化极大值 
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        clor[x][y]=c+1;
    }
    dfs(1,1,0,0);
    if(flag==1)
    {
        printf("%d
",money[m][m]);
    }
    else
    {
        printf("-1
");
    }
    
    return 0;
}