刷题笔记：Luogu P3956 棋盘

Problem

Solution

DFS/BFS

需要注意去重的时候可以重复走（因为有限定条件），只要新的步数比原来的步数小就可以走，其余情况模拟即可

细节有点多，比如需要记录一下上一步的棋盘颜色（下一次搜索传递参数），因为牵扯到使用魔法问题，不能直接染，因为改变地图后后边很多操作都会受影响

在列举可能性的时候需要注意如果棋盘没颜色且不满足使用魔法，在列举颜色不同条件时需要特判棋盘有颜色 被卡了2 days啊

然后实现的时候注意细节，然后就没有然后了

Code

// By SXqwq
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int m,n;
int mapp[N][N];
int vis[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
void dfs(int x,int y,int val)
{
    if(vis[x][y]>vis[m][m]) return; //剪枝
    for(int i=0;i<4;i++)
    {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if(!(ax>=1&&ax<=m&&ay>=1&&ay<=m)) continue;
        if(!mapp[ax][ay] && vis[x][y] + 2 < vis[ax][ay] && mapp[x][y])
        {
            vis[ax][ay] = vis[x][y] + 2;
            dfs(ax,ay,val);
        }
        else if(mapp[ax][ay] == val && vis[x][y] < vis[ax][ay])
        {
            vis[ax][ay] = vis[x][y];
            dfs(ax,ay,val);
        }
        else if(mapp[ax][ay] != val && mapp[ax][ay] && vis[x][y] + 1 < vis[ax][ay]) //注意特判棋盘有颜色！
        {
            vis[ax][ay] = vis[x][y] + 1;
            dfs(ax,ay,mapp[ax][ay]);
        }
    }
}
int main()
{
    memset(vis,INF,sizeof(vis));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        mapp[x][y] = c+1;
    }
    vis[1][1] = 0;
    dfs(1,1,mapp[1][1]);
    if(vis[m][m] == INF) cout<<"-1"<<endl;
    else cout<<vis[m][m]<<endl;
    return 0;
}