ACWing471. 棋盘-DFS剪枝

admin2024-05-15  1

题目

ACWing471. 棋盘-DFS剪枝,第1张

ACWing471. 棋盘-DFS剪枝,第2张

ACWing471. 棋盘-DFS剪枝,第3张

思路

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

ACWing471. 棋盘-DFS剪枝,第4张

ACWing471. 棋盘-DFS剪枝,第5张

ACWing471. 棋盘-DFS剪枝,第6张

约束方程: 

ACWing471. 棋盘-DFS剪枝,第7张

代码

#include <iostream>
#include <cstring>
#include <algorithm>

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 | 璃月森林探险:符文之路 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!