首页 > 代码库 > HDU 1010 Tempter of the Bone

HDU 1010 Tempter of the Bone

2024-07-15 19:03:12   223人阅读

第一次剪枝，只不过不是我自己剪的，学习别人的代码。

我感觉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 }
代码君

 


联系
我们