- 浏览: 309276 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
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 1092KIDx 的解题报告 题意很简单:http://acm.hdu ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2498http://acm.hdu.edu.cn/showprobl ... -
【最短路/3大模板】总结【2012-1-22新增前插的spfa】
2011-08-28 18:15 2874首先献上模板:【点都是默认为从1到n编号,用dijk和f ... -
【优先队列广搜+前驱记录】HDU 1026 Ignatius and the Princess I
2011-08-22 10:07 2927http://acm.hdu.edu.cn/showprobl ... -
【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest
2011-08-15 15:21 2178http://acm.hdu.edu.cn/showprobl ... -
【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数
2011-07-28 11:23 1989http://acm.hdu.edu.cn/showprobl ... -
HDU 1175 连连看【2011年11月14号更新】
2011-06-02 17:00 1664http://acm.hdu.edu.cn/showprobl ... -
HDU_1501_Zipper
2011-06-02 16:48 938http://acm.hdu.edu.cn/showprobl ... -
HDU 1010 Tempter of the Bone
2011-06-02 16:39 2158http://acm.hdu.edu.cn/showprobl ... -
HDU 1258 Sum It Up
2011-06-02 16:16 1229http://acm.hdu.edu.cn/showprobl ... -
HDU_1495_非常可乐
2011-06-02 13:26 1076http://acm.hdu.edu.cn/showprobl ... -
POJ 2676 Sudoku
2011-05-13 22:50 1355http://poj.org/problem?id=2676 ... -
POJ_2488_A Knight's Journey
2011-05-13 22:45 909http://poj.org/problem?id=2488 ... -
POJ_1088_滑雪
2011-05-13 22:21 781http://poj.org/problem?id=1088 ...
相关推荐
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
acm hdu as easy as a+b
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
HDU1059的代码
杭电ACMhdu1163
HDU的一题........HDU DP动态规
hdu1001解题报告
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu2101AC代码