P3956棋盘 ( dfs + 剪枝

这篇具有很好参考价值的文章主要介绍了P3956棋盘 ( dfs + 剪枝。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[110][110];
int vis[110][110];
int f[110][110];
int res = 0x3f3f3f3f;
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};

void dfs(int x, int y, int col, int coat){

    if(coat >= f[x][y])return;

    f[x][y] = coat;

    if(x == m && y == m){
        res =  min(res,coat);
        return;
    }
    vis[x][y] = 1;
    for(int i=0;i<4;i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx>=1 && xx<=m && yy>=1 && yy<=m && !vis[xx][yy]){
            if(col == a[xx][yy]){
                dfs(xx,yy,a[xx][yy],coat);
            }else if(col != a[xx][yy]){
                if(a[xx][yy] == 0 && col == a[x][y]){
                    dfs(xx,yy,col,coat+2);
                }else if(a[xx][yy] != 0){
                    dfs(xx,yy,a[xx][yy],coat+1);
                }
            }
        }
    }

    vis[x][y] = 0;
}


int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int x,y,c;
        cin>>x>>y>>c;
        a[x][y] = c+1;
    }
    memset(f,127,sizeof f);
    dfs(1,1,a[1][1],0);
    if(res == 0x3f3f3f3f){
        puts("-1");
    }else{
        printf("%d",res);
    }

}

本质上来说并不是特别复杂的搜索,只不过这个搜索时要维护多个状态量,没怎么做过属于是

同时有一个剪枝就是维护走到 (i,j)的最短花费,大于这个花费就直接减掉文章来源地址https://www.toymoban.com/news/detail-536358.html

到了这里,关于P3956棋盘 ( dfs + 剪枝的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

原文地址:https://blog.csdn.net/m0_75125820/article/details/131593949

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

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包