当前位置: 首页 > news >正文

网站开发费会计处理湖南疫情最新消息今天

网站开发费会计处理,湖南疫情最新消息今天,免费申请网页,济南网站建设价格【题目链接】 洛谷 P3956 [NOIP2017 普及组] 棋盘 ybt 1416:【17NOIP普及组】棋盘 【题目考点】 1. 深搜:深搜回溯 2. 深搜剪枝:最优化剪枝 【解题思路】 搜索从左上角到右下角的所有走法中花费金币最少的走法。 需要使用深搜回溯&…

【题目链接】

洛谷 P3956 [NOIP2017 普及组] 棋盘
ybt 1416:【17NOIP普及组】棋盘

【题目考点】

1. 深搜:深搜回溯
2. 深搜剪枝:最优化剪枝

【解题思路】

搜索从左上角到右下角的所有走法中花费金币最少的走法。
需要使用深搜回溯,搜索从一点出发到另一点的所有路径。
设二维数组mp记录每个格子的颜色,如果无色记为-1,1是黄色,0是红色。
在某次搜索时,当前位置为(sx, sy),下一个要访问的位置为(x, y),已经使用金币coin。
如果当前位置(sx,sy)是有色的

  • 如果下一个位置(x,y)是有色的
    • 如果二者颜色相同,到下个位置时花的金币数coin不变
    • 如果颜色不同,到下个位置花的金币数coin加1。
  • 如果下一个位置(x,y)是无色的
    • 将下一个位置通过魔法变为与(sx, sy)同色,到下个位置的金币数coin加2,

如果当前位置(sx, sy)是无色的,但是变成了col色。那么下个位置(x, y)不可以是无色的。
如果下个位置(x,y)是有色的,那么

  • 如果(x,y)位置的颜色和col相同,那么到下个位置时花的金币数coin不变
  • 如果(x,y)位置的颜色和col不同,到下个位置花的金币数coin加1。

设二维数组mc,mc[i][j]表示到达(i, j)位置时花的最少金币数。
最优性剪枝:如果到(sx, sy)位置花的钱数coin比已知的一种到(sx, sy)位置的走法花钱mc[sx][sy]相等或更多,则没必要再搜索了,直接返回。
这里必须进行最优性剪枝,否则搜索会超时。

【题解代码】

解法1:深搜
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
int m, n, mp[N][N], minCoin = INF, mc[N][N];//mp[i][j]:为1代表黄色,0代表红色,-1代表无色 mc[i][j],到i,j的最小钱数 
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
bool vis[N][N];
void dfs(int sx, int sy, int coin, int col)//col:如果(sx,sy)本来是无色,col为(sx,sy)通过魔法变化后的颜色 
{if(coin >= mc[sx][sy])//最优化剪枝,如果到当前位置花的钱数比已知的一种到当前位置的走法花钱更多,则没必要再搜索了。 return;elsemc[sx][sy] = coin;if(sx == m && sy == m)//到达终点点 return; for(int i = 0; i < 4; ++i){int x = sx + dir[i][0], y = sy + dir[i][1];//x,y是sx,sy周围的位置 if(x >= 1 && x <= m && y >= 1 && y <= m && !vis[x][y]){vis[x][y] = true;if(mp[sx][sy] == 1 || mp[sx][sy] == 0)//如(sx, sy)是红黄 {if(mp[x][y] == -1)//如果下一个位置无色 dfs(x, y, coin + 2, mp[sx][sy]);//变成与出发点相同的颜色 else if(mp[x][y] == mp[sx][sy])//颜色相同 dfs(x, y, coin, -1);else//颜色不同 dfs(x, y, coin + 1, -1);}else if(mp[sx][sy] == -1 && mp[x][y] != -1)//如(sx, sy)是无色 {//如果无色的下一个格子还是无色,则不访问 if(mp[x][y] == col)//颜色相同 dfs(x, y, coin, -1);						else//颜色不同 dfs(x, y, coin + 1, -1);}vis[x][y] = false;}}
}
int main()
{int x, y, c;memset(mp, -1, sizeof(mp));cin >> m >> n;for(int i = 1; i <= n; ++i){cin >> x >> y >> c;mp[x][y] = c;}memset(mc, 0x3f, sizeof(mc));dfs(1, 1, 0, -1);if(mc[m][m] == INF)cout << -1;elsecout << mc[m][m];return 0;
}
http://www.hrbkazy.com/news/20346.html

相关文章:

  • 深圳网站制作公司讯息seo查询 站长工具
  • 重庆小程序开发公司全网营销与seo
  • 网站建设基本费用佛山做网络优化的公司
  • 公司网站建设30元网站搜索排名优化价格
  • 建站优化收费新闻源
  • 网站discuz迁移怎么做网络营销有哪些
  • asp做企业网站很好啊十大计算机培训学校
  • 武汉工程造价咨询公司杭州百度推广优化排名
  • 佛山网站建设价格汕头seo快速排名
  • 怎么找网站做宣传百度问答我要提问
  • 网站信息化建设方案无锡网站优化
  • 做网站日入100怎样推广自己的店铺啊
  • 网站买了服务器后该怎么做做灰色词seo靠谱
  • 宁城网站建设公司如何快速收录一个网站的信息
  • seo关键词排名如何seo方法培训
  • 坂田网站建设推广公司合肥网站排名提升
  • 云适配 网站产品50个关键词
  • 在线学习网站开发江苏网站开发
  • 那个做网站好seo技术介绍
  • 中小型网站建设哪家好厦门seo外包公司
  • 广州网站建设费用有什么平台可以推广信息
  • 购物网站设计理念滨州seo排名
  • 韩国手机网站模板小程序开发平台有哪些
  • 专业做域名的网站吗广州网站排名优化公司
  • wordpress常用技巧南宁优化推广服务
  • 免费 成品模板网站培训机构加盟店排行榜
  • 长沙网站建设服务商谷歌商店官网下载
  • php做的大型网站网上宣传广告怎么做
  • 牌具做网站最新新闻热点事件2023
  • 网站的网站建设企业地推扫码平台