- 浏览: 316186 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
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 1133KIDx 的解题报告 题意很简单:http://acm.hdu ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2537http://acm.hdu.edu.cn/showprobl ... -
【最短路/3大模板】总结【2012-1-22新增前插的spfa】
2011-08-28 18:15 2928首先献上模板:【点都是默认为从1到n编号,用dijk和f ... -
【优先队列广搜+前驱记录】HDU 1026 Ignatius and the Princess I
2011-08-22 10:07 2971http://acm.hdu.edu.cn/showprobl ... -
【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest
2011-08-15 15:21 2207http://acm.hdu.edu.cn/showprobl ... -
【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数
2011-07-28 11:23 2038http://acm.hdu.edu.cn/showprobl ... -
HDU 1175 连连看【2011年11月14号更新】
2011-06-02 17:00 1707http://acm.hdu.edu.cn/showprobl ... -
HDU_1501_Zipper
2011-06-02 16:48 973http://acm.hdu.edu.cn/showprobl ... -
HDU 1010 Tempter of the Bone
2011-06-02 16:39 2187http://acm.hdu.edu.cn/showprobl ... -
HDU 1258 Sum It Up
2011-06-02 16:16 1260http://acm.hdu.edu.cn/showprobl ... -
HDU_1495_非常可乐
2011-06-02 13:26 1111http://acm.hdu.edu.cn/showprobl ... -
POJ 2676 Sudoku
2011-05-13 22:50 1382http://poj.org/problem?id=2676 ... -
POJ_2488_A Knight's Journey
2011-05-13 22:45 934http://poj.org/problem?id=2488 ... -
POJ_1088_滑雪
2011-05-13 22:21 814http://poj.org/problem?id=1088 ...
相关推荐
HDU(杭州电子科技大学)在线评测系统是许多编程竞赛爱好者和学习者经常访问的平台,它提供了大量的算法题目供用户练习和挑战。这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、...
ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...
《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
"hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
在C++编程语言中,`new`和`delete`是两个关键的操作符,它们与C语言中的`malloc`和`free`有所不同。`new`不仅分配内存,还会根据指定的类型调用对应的构造函数来初始化对象,而`malloc`仅仅分配内存,不涉及对象的...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
* 题目1072:Nightmare,涉及到完全搜索的概念。 4. 图的匹配:图的匹配算法、图的稳定匹配等。 * 题目1104:Remainder,涉及到图的匹配算法。 * 题目1105:The Wolves and the Sheep,涉及到图的稳定匹配概念。 5...
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...
HDU1059的代码