首页 > 代码库 > HDU 1010 Tempter of the Bone
HDU 1010 Tempter of the Bone
第一次剪枝,只不过不是我自己剪的,学习别人的代码。
我感觉ACM一开始就是学习学习在学习,等弄懂一定量的题目以后,才会慢慢有自己的思路,自己的风格。
题意:有一个迷宫,给出一个起点和终点,问能否正好在第t步走到终点,每个方格只能走一遍。
两次剪枝都在代码注释里面。
这是搜索的第一篇,加油↖(^ω^)↗
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 8 char map[10][10]; 9 int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};10 int flag, Sx, Sy, Dx, Dy, Xnum;11 int n, m, t;12 13 void DFS(int x, int y, int time)14 {15 if(x<1 || x>n || y<1 || y>m)16 return;17 if(flag == 1)18 return;19 if(x == Dx && y == Dy && time == t)20 {21 flag = 1;22 return;23 }24 25 int temp = (t-time) - abs(x-Dx) - abs(y-Dy);26 if(temp<0 || temp&1) //剩余时间不足或者奇偶性不同,剪枝27 return;28 for(int i = 0; i < 4; ++i)29 {30 int x1 = x + dir[i][0];31 int y1 = y + dir[i][1];32 if(map[x1][y1] != ‘X‘)33 {34 map[x1][y1] = ‘X‘;35 DFS(x1, y1, time + 1);36 map[x1][y1] = ‘.‘;37 }38 }39 return;40 }41 42 int main(void)43 {44 #ifdef LOCAL45 freopen("1010in.txt", "r", stdin);46 #endif47 48 while(cin >> n >> m >> t)49 {50 if(n==0 && m==0 && t==0)51 break;52 Xnum = 0;53 for(int i = 1; i <= n; ++i)54 for(int j = 1; j <= m; ++j)55 {56 cin >> map[i][j];57 if(map[i][j] == ‘S‘)58 {59 Sx = i;60 Sy = j;61 }62 if(map[i][j] == ‘D‘)63 {64 Dx = i;65 Dy = j;66 }67 if(map[i][j] == ‘X‘)68 ++Xnum;69 }70 flag = 0;71 map[Sx][Sy] = ‘X‘;72 73 if(n*m - Xnum <= t)74 { //所给t过大,剪枝75 printf("NO\n");76 continue;77 }78 DFS(Sx, Sy, 0);79 if(flag)80 printf("YES\n");81 else82 printf("NO\n");83 }84 return 0;85 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。