- 浏览: 321376 次
- 性别:
- 来自: 珠海
-
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
KIDx 的解题报告
HDU 1728 逃离迷宫 http://acm.hdu.edu.cn/showproblem.php?pid=1728
对于代码31行,为什么等于不能随便剪掉
如果剪掉就会出现下图结果:
【假如转弯数k=1,起点终点如图】
那么如果你的代码是优先向右搜索就会出错
红色的线是先搜的,由于最多转一次弯,所以不合题意;
蓝色是后搜的,因为遇到转弯数相等所以不往下走了了,但是继续走是可以满足题意输出"yes"的
深搜:
融合深搜思想的广搜【单方向优先扩展】
HDU 1072 Nightmare http://acm.hdu.edu.cn/showproblem.php?pid=1072
深搜
广搜
HDU 1728 逃离迷宫 http://acm.hdu.edu.cn/showproblem.php?pid=1728
对于代码31行,为什么等于不能随便剪掉
如果剪掉就会出现下图结果:
【假如转弯数k=1,起点终点如图】
那么如果你的代码是优先向右搜索就会出错
红色的线是先搜的,由于最多转一次弯,所以不合题意;
蓝色是后搜的,因为遇到转弯数相等所以不往下走了了,但是继续走是可以满足题意输出"yes"的

深搜:

#include <iostream> using namespace std; #define inf 0x3fffffff #define M 105 //1、wan用于转弯数剪枝;2、step用于步数剪枝,就不用vis标记访问了 int r, c, ex, ey, k, wan[M][M]; char map[M][M]; int x_move[4] = {-1, 0, 1, 0}; int y_move[4] = {0, 1, 0, -1}; bool flag; void dfs (int x, int y, int dir) //dir为当前方向 { if (x == ex && y == ey) { if (wan[x][y] <= k) flag = true; return ; } if (wan[x][y] > k) //转弯数超过k不用往下走了 return ; //x !=ex && y != ey 说明必须至少再转一次弯,但是已经不能再转了 if (wan[x][y] == k && x !=ex && y != ey) return ; for (int i = 0; i < 4; i++) { int tx = x + x_move[i]; int ty = y + y_move[i]; if (tx < 0 || tx >= r || ty < 0 || ty >= c) continue; //转弯数相等不可剪掉,所以是wan[tx][ty] < wan[x][y]而不是wan[tx][ty] <= wan[x][y] if (map[tx][ty] == '*' || wan[tx][ty] < wan[x][y]) //转弯数剪枝 continue; if (dir != -1 && i != dir && wan[tx][ty] < wan[x][y] + 1) //转弯数剪枝 continue; wan[tx][ty] = wan[x][y]; if (dir != -1 && i != dir) wan[tx][ty]++; //如果方向变了转弯+1 dfs (tx, ty, i); if (flag) return ; } } int main() { int t, i, j, sx, sy; //sx, sy是起点 scanf ("%d", &t); while (t--) { scanf ("%d%d", &r, &c); for (i = 0; i < r; i++) scanf ("%s", map[i]); scanf ("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex); sx--, sy--, ex--, ey--; //我从0开始编号,而题目是从1开始 for (i = 0; i < r; i++) for (j = 0; j < c; j++) wan[i][j] = inf; //初始化转弯数和步数为无穷大 wan[sx][sy] = 0; //到达起点的转弯数 flag = false; dfs (sx, sy, -1); //一开始可以走任意方向,所以设方向为-1 if (flag) puts ("yes"); else puts ("no"); } return 0; }
融合深搜思想的广搜【单方向优先扩展】

#include <iostream> #include <queue> using namespace std; #define inf 0x3fffffff #define M 105 int r, c, sx, sy, ex, ey, wan[M][M], t, k; char map[M][M]; int x_move[4] = {-1, 0, 1, 0}; int y_move[4] = {0, 1, 0, -1}; struct pos{ int x, y; }; void bfs () { int i, j; for (i = 0; i < r; i++) for (j = 0; j < c; j++) wan[i][j] = inf; pos ft, tp; ft.x = sx, ft.y = sy; wan[ft.x][ft.y] = -1; queue<pos> q; q.push (ft); while (!q.empty()) { ft = q.front(); q.pop(); if (ft.x == ex && ft.y == ey && wan[ft.x][ft.y] <= k) { puts ("yes"); return ; } for (i = 0; i < 4; i++) { tp.x = ft.x + x_move[i]; tp.y = ft.y + y_move[i]; while (!(tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c)) { if (map[tp.x][tp.y] == '*') break; if (wan[tp.x][tp.y] < wan[ft.x][ft.y] + 1) break; wan[tp.x][tp.y] = wan[ft.x][ft.y] + 1; if (wan[tp.x][tp.y] > k) break; if (wan[tp.x][tp.y] == k && tp.x != ex && tp.y != ey) break; q.push (tp); tp.x += x_move[i]; tp.y += y_move[i]; //单方向优先扩展 } } } puts ("no"); } int main() { int t, i; scanf ("%d", &t); while (t--) { scanf ("%d%d", &r, &c); for (i = 0; i < r; i++) scanf ("%s", map[i]); scanf ("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex); sx--, sy--, ex--, ey--; bfs (); } return 0; }
HDU 1072 Nightmare http://acm.hdu.edu.cn/showproblem.php?pid=1072
深搜
#include <iostream> using namespace std; #define inf 0x3fffffff #define M 10 //step[i][j]表示从起点到ij需要的最小步数,T[i][j]表示走到ij诈弹还剩下的时间 int r, c, mins; int map[M][M], step[M][M], T[M][M]; int x_move[4] = {-1, 0, 1, 0}; int y_move[4] = {0, 1, 0, -1}; void dfs (int x, int y) { if (T[x][y] <= 0) //炸死了 return ; if (map[x][y] == 3) { if (step[x][y] < mins) mins = step[x][y]; return ; } for (int i = 0; i < 4; i++) { int tx = x + x_move[i]; int ty = y + y_move[i]; if (tx < 0 || tx >= r || ty < 0 || ty >= c) continue; if (map[tx][ty] == 0 || step[tx][ty] <= step[x][y] + 1 && T[tx][ty] >= T[x][y] - 1) continue; //已访问过,而且如果走下去诈弹时间没变甚至变小,那还不如不走呢 step[tx][ty] = step[x][y] + 1; T[tx][ty] = T[x][y] - 1; if (map[tx][ty] == 4 && T[tx][ty] > 0) T[tx][ty] = 6; //将诈弹时间置为6,按照题意走到txty必须诈弹还有剩余时间,否则还是要爆 dfs (tx, ty); } } int main() { int t, i, j, sx, sy; scanf ("%d", &t); while (t--) { scanf ("%d %d", &r, &c); for (i = 0; i < r; i++) { for (j = 0; j < c; j++) { scanf ("%d", map[i]+j); if (map[i][j] == 2) sx = i, sy = j; step[i][j] = inf; //初始化步数为无穷大 } } step[sx][sy] = 0; //到起点的最小步数是0 memset (T, 0, sizeof(T)); //初始化诈弹剩余时间为0 T[sx][sy] = 6; //起点的诈弹初始时间为6 mins = inf; dfs (sx, sy); if (mins == inf) puts ("-1"); else printf ("%d\n", mins); } return 0; }
广搜
#include <iostream> #include <queue> using namespace std; #define inf 0x3fffffff #define M 10 int sx, sy, step[M][M], T[M][M], r, c; int x_move[4] = {-1, 0, 1, 0}; int y_move[4] = {0, 1, 0, -1}; int map[M][M]; struct pos{ int x, y; }; void bfs () { int i, j; for (i = 0; i < r; i++) for (j = 0; j < c; j++) step[i][j] = inf, T[i][j] = 0; pos ft, tp; ft.x = sx, ft.y = sy; step[ft.x][ft.y] = 0; T[ft.x][ft.y] = 6; queue <pos> q; q.push (ft); while (!q.empty()) { ft = q.front(); q.pop(); if (map[ft.x][ft.y] == 3 && T[ft.x][ft.y] > 0) { printf ("%d\n", step[ft.x][ft.y]); return ; } for (i = 0; i < 4; i++) { tp.x = ft.x + x_move[i]; tp.y = ft.y + y_move[i]; if (tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c) continue; if (map[tp.x][tp.y] == 0) continue; if (step[tp.x][tp.y] <= step[ft.x][ft.y] + 1 && T[tp.x][tp.y] >= T[ft.x][ft.y] - 1) continue; step[tp.x][tp.y] = step[ft.x][ft.y] + 1; T[tp.x][tp.y] = T[ft.x][ft.y] - 1; if (T[tp.x][tp.y] <= 0) continue; if (map[tp.x][tp.y] == 4) T[tp.x][tp.y] = 6; q.push (tp); } } puts ("-1"); } int main() { int t, i, j; scanf ("%d", &t); while (t--) { scanf ("%d%d", &r, &c); for (i = 0; i < r; i++) { for (j = 0; j < c; j++) { scanf ("%d", map[i]+j); if (map[i][j] == 2) sx = i, sy = j; } } bfs (); } return 0; }
发表评论
-
LOJ 1009 Back to Underworld
2012-01-10 16:50 0KIDx 的解题报告 题目链接:http://ligh ... -
HDU 2579 Dating with girls(2)
2011-12-02 11:51 1151KIDx 的解题报告 题意很简单:http://acm.hdu ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2548http://acm.hdu.edu.cn/showprobl ... -
【最短路/3大模板】总结【2012-1-22新增前插的spfa】
2011-08-28 18:15 2967首先献上模板:【点都是默认为从1到n编号,用dijk和f ... -
【优先队列广搜+前驱记录】HDU 1026 Ignatius and the Princess I
2011-08-22 10:07 3011http://acm.hdu.edu.cn/showprobl ... -
【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest
2011-08-15 15:21 2227http://acm.hdu.edu.cn/showprobl ... -
【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数
2011-07-28 11:23 2067http://acm.hdu.edu.cn/showprobl ... -
HDU 1175 连连看【2011年11月14号更新】
2011-06-02 17:00 1725http://acm.hdu.edu.cn/showprobl ... -
HDU_1501_Zipper
2011-06-02 16:48 1003http://acm.hdu.edu.cn/showprobl ... -
HDU 1010 Tempter of the Bone
2011-06-02 16:39 2203http://acm.hdu.edu.cn/showprobl ... -
HDU 1258 Sum It Up
2011-06-02 16:16 1287http://acm.hdu.edu.cn/showprobl ... -
HDU_1495_非常可乐
2011-06-02 13:26 1144http://acm.hdu.edu.cn/showprobl ... -
POJ 2676 Sudoku
2011-05-13 22:50 1421http://poj.org/problem?id=2676 ... -
POJ_2488_A Knight's Journey
2011-05-13 22:45 962http://poj.org/problem?id=2488 ... -
POJ_1088_滑雪
2011-05-13 22:21 828http://poj.org/problem?id=1088 ...
相关推荐
"HDU1072 Nightmare.cpp"可能涉及到深度优先搜索在解决复杂问题中的应用,如梦境解析;"HDU1016 Prime Ring Problem.cpp"可能使用了BFS寻找素数环;"HDU1015 Safecracker.cpp"可能通过BFS算法破解密码锁;"HDU1238 ...
街道级行政区划shp矢量数据,wgs84坐标系,下载直接使用
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
街道级行政区划shp矢量数据,wgs84坐标系,下载直接使用
轻量级密码算法LBlock的FPGA优化实现.docx
街道级行政区划shp矢量数据,wgs84坐标系,下载直接使用
Git 资料 progit-zh-v2.1.1.pdf
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
篮球计分器FPGA附程序..doc
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
内容概要:本文档全面介绍了Linux开发的基础知识、应用场景、环境搭建、常用命令、Shell脚本编程以及C/C++和Python开发等内容。首先阐述了Linux开发的重要性及其在服务器端开发、嵌入式开发和系统运维等领域的广泛应用。接着详细讲解了如何选择合适的Linux发行版并安装系统,配置开发环境,包括安装必要的开发工具和配置SSH服务。文档还深入讲解了Linux基础命令,如文件和目录操作、文件内容查看与编辑、进程管理和权限管理。此外,介绍了Shell脚本编程的基本语法,包括变量、条件语句、循环语句和函数定义。针对C/C++和Python开发,文档分别讲解了编译器安装、程序编写与编译、调试方法及使用虚拟环境等内容。最后,简要介绍了Linux内核开发的相关知识,包括下载编译内核、内核模块开发等,并推荐了相关学习资源。 适合人群:对Linux开发感兴趣的初学者及有一定经验的研发人员,尤其是希望深入掌握Linux开发技能的开发者。 使用场景及目标:①掌握Linux开发环境的搭建与配置;②熟悉Linux基础命令和Shell脚本编程;③学习C/C++和Python在Linux下的开发流程;④了解Linux内核开发的基本概念和技术。 阅读建议:此文档内容丰富,涵盖面广,建议读者根据自身需求选择性阅读,并结合实际操作进行练习。特别是对于初学者,应先掌握基础命令和开发环境的搭建,再逐步深入到编程语言和内核开发的学习。
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
街道级行政区划shp数据,wgs84坐标系,直接使用。
内容概要:本文档《word练习题.docx》是一份详细的Word操作练习指南,涵盖了从基础到高级的各种功能。文档分为三个主要部分:内容编辑、页面布局和高效文档。内容编辑部分包括文本格式化、段落设置、项目编号、制表位、边框与底纹等练习;页面布局部分涉及分节符、分栏、页眉页脚、水印等设置;高效文档部分则聚焦于样式管理、导航窗格、题注、书签、超级链接、脚注与尾注、交叉引用等功能。每个练习都有具体的操作步骤,帮助用户掌握Word的各种实用技巧。 适合人群:适用于Word初学者及希望提高Word技能的中级用户,尤其是需要频繁使用Word进行文档编辑和排版的办公人员。 使用场景及目标:①帮助用户熟悉Word的基本操作,如文本编辑、格式设置等;②提升用户的文档排版能力,学会设置复杂的页面布局;③提高工作效率,掌握高效文档管理技巧,如样式应用、题注和交叉引用等。 其他说明:此文档不仅提供了具体的练习题目,还附带了详细的步骤说明,用户可以根据指引逐步完成每个练习。此外,文档中的一些练习涉及到智能文档和Office智能客户端的应用,有助于用户了解Word在企业级应用中的潜力。建议用户按照章节顺序逐步学习,实践每一个练习,以达到最佳的学习效果。
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
全球腐败感知数据(2000-2023)——3000行 33个指标 关于数据集 该数据集包含3000行和33列,涵盖了2000年至2023年的腐败感知指数(CPI)数据和各种治理指标。它包括国家排名、分数和其他指标,如公共部门腐败、司法腐败、贿赂指数、商业道德、民主指数、法治、政府效率、经济指标和人类发展指数。 这些数据可用于: 腐败趋势分析 腐败对GDP、人类发展指数和治理的影响 跨国比较 数据可视化和机器学习模型 该数据集对研究人员、数据分析师、政策制定者和对研究全球腐败趋势非常有用。
毕业设计(论文) 基于FPGA的数字频率计设计.doc
街道级行政区划shp数据,wgs84坐标系,直接使用。
NTI1NDU3NTAyODMwOTQxMzI0M18xNzQ0Nzk1MTk1OTgz_6.JPG