首页 > 代码库 > HDU 1010 深搜+奇偶剪枝
HDU 1010 深搜+奇偶剪枝
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1010
贴个资料：
http://acm.hdu.edu.cn/forum/read.php?tid=6158
奇偶剪枝：
对于从起始点 s 到达终点 e，走且只走 t 步的可达性问题的一种剪枝策略。
如下列矩阵 ：
从任意 0 到达 任意 0，所需步数均为偶数，到达任意 1 ，均为奇数。反之亦然
所以有，若s走且只走 t 步可到达e，则必有t >= abs(s.x - e.x) + abs(s.y - e.y)，且 (t&1) == ((abs(s.x - e.x) + abs(s.y - e.y))&1)。
否则必不可达。
1 #include<cstdio> 2 #include<cstdlib> 3 using namespace std; 4 char maze[10][10]; 5 int dx[4] = { -1, 1, 0, 0 }; 6 int dy[4] = { 0, 0, -1, 1 }; 7 int sx, sy, ex, ey; 8 bool escape; 9 void dfs(int t, int x, int y)10 {11 if (maze[x][y] == ‘D‘&&t == 0 || escape)12 {13 escape = true; return;14 }15 char tmp = maze[x][y];16 maze[x][y] = ‘X‘;17 int T = t - abs(ex - x) - abs(ey - y);18 if (T >= 0 && T % 2 == 0)19 {20 for (int i = 0; i < 4; i++)21 {22 int r = dx[i] + x, c = dy[i] + y;23 if (maze[r][c] == ‘.‘ || maze[r][c] == ‘D‘)24 dfs(t - 1, r, c);25 }26 }27 maze[x][y] = tmp;28 }29 int main()30 {31 int n, m, t;32 while (scanf("%d%d%d", &n, &m, &t) && n)33 {34 for (int i = 1; i <= n; i++)35 scanf("%s", maze[i]+1);36 for (int i = 1; i <= n; i++)37 {38 for (int j = 1; j <= m; j++)39 {40 if (maze[i][j] == ‘S‘)41 sx = i, sy = j;42 if (maze[i][j] == ‘D‘)43 ex = i, ey = j;44 }45 }46 escape = false;47 dfs(t, sx, sy);48 printf(escape ? "YES\n" : "NO\n");49 }50 return 0;51 }
HDU 1010 深搜+奇偶剪枝
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。