ACWing471. 棋盘-DFS剪枝

题目

思路

本思路参考博客AcWing 471. 棋盘 - AcWing

约束方程： 

代码

#include 
#include 
#include 
 
using namespace std;
 
const int N = 110, INF = 0x3f3f3f3f;
int g[N][N], n, m, dist[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
 
void dfs(int x, int y, int cost, int used) 
{
    if (dist[x][y] <= cost) return ; //花费更少，说明没必要DFS，直接剪枝
 
    dist[x][y] = cost;
 
    if (x == m && y == m) return ;
 
    for (int i = 0; i < 4; i ++ ) //四个方向深搜
    {
        int nx = x + dx[i], ny = dy[i] + y;
        if (nx < 1 || nx > m || ny < 1 || ny > m) continue ;
 
        if (g[nx][ny] == -1)  //无颜色
        {
            if (used) continue ; //已经使用魔法的不能再次使用
            else {
                g[nx][ny] = g[x][y];
                dfs(nx, ny, cost + 2, 1);
                g[nx][ny] = -1;
            }
        }
        else if (g[nx][ny] == g[x][y]) dfs(nx, ny, cost, 0);//颜色相同
        else dfs(nx, ny, cost + 1, 0);//颜色不同，使用魔法
    }
}
 
int main() 
{
    scanf("%d%d", &m, &n);
 
    memset(g, -1, sizeof g);
    while (n -- ) 
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = c;
    }
    memset(dist, 0x3f, sizeof dist);
 
    dfs(1, 1, 0, 0);
    if (dist[m][m] == INF) puts("-1");
    else printf("%d\n", dist[m][m]);
 
    return 0;
}

xmuoj：xmuoj | 璃月森林探险：符文之路