冀教网 - 河北教师网站 - 专注于冀教版课本资源

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 83|回复: 0

P3956 棋盘

[复制链接]

4万

主题

4万

帖子

12万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
124999
发表于 2020-5-24 04:07 | 显示全部楼层 |阅读模式
题目描述

有一个m×m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的), 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你不需要花费金币;如果不同,则你需要花费 1个金币。
另外, 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用, 而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走到了这个暂时有颜色的格子上,你就不能继续使用魔法; 只有当你离开这个位置,走到一个本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔法使得变为有颜色的格子)时,这个格子恢复为无色。
现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?
输入格式

第一行包含两个正整数m, nm,n,以一个空格分开,分别代表棋盘的大小,棋盘上有颜色的格子的数量。
接下来的nn行,每行三个正整数x, y, cx,y,c, 分别表示坐标为(x,y)的格子有颜色cc。
其中c=1c=1 代表黄色,c=0c=0 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为(1,1),右下角的坐标为(m,m)。
棋盘上其余的格子都是无色。保证棋盘的左上角,也就是(1,1) 一定是有颜色的。
输出格式

一个整数,表示花费的金币的最小值,如果无法到达,输出1。
我的关键词 P3956 棋盘  新闻资讯 1685879-20200524031932024-2102354897


我的关键词 P3956 棋盘  新闻资讯 1685879-20200524032048086-1921494481

我的关键词 P3956 棋盘  新闻资讯 1685879-20200524032259022-2132730452

——————————————————————————————————
求最小值,似乎用BFS更优。。。
本人还是用DFS做的这道题目。可以用一个二维数组money[][]来记录到各个点时的最小花费(用以剪枝),那么在遍历到点(x,y)时,若当前花费大于等于money[x][y],那么就没有进行下去的必要了,可以直接返回;同样,当当前花费大于等于已求出的最小花费,同样没有继续下去的必要了。遇到没有颜色的点时,需要判断当前这一步是否可以使用魔法,因此可以用一个参数来记录(我用的是一个bool型的,当然int也可以)。
直接上代码:
  1. #include int m, n, cost;int chessBoard[105][105];int money[105][105];//上,下,左,右const int dx[4] = {-1, 1, 0, 0};const int dy[4] = {0, 0, -1, 1};void DFS(int x, int y, int curCost, bool used);using namespace std;int main(){    cin >> m >> n;    //将棋盘初始化为无颜色的    for(int r = 0; r > y >> color;        chessBoard[x][y] = color;    }    cost = 50000;    DFS(1, 1, 0, false);    if(cost == 50000)        cout = money[x][y])        return;    else        money[x][y] = curCost;    for(int i = 0; i < 4; i++){        int cur_x = x + dx[i];        int cur_y = y + dy[i];        if(chessBoard[cur_x][cur_y] != -1){            if(chessBoard[cur_x][cur_y] == chessBoard[x][y])                DFS(cur_x, cur_y, curCost, false);            else                DFS(cur_x, cur_y, curCost+1, false);        }else if(!used){            chessBoard[cur_x][cur_y] = chessBoard[x][y];            DFS(cur_x, cur_y, curCost+2, true);            chessBoard[cur_x][cur_y] = -1;        }    }}
复制代码


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|冀教网 - 河北教师网站 - 专注于冀教版课本资源  

GMT+8, 2020-6-6 18:33 , Processed in 0.328735 second(s), 30 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表