首页 > 代码库 > HDU 1312 Red and Black

HDU 1312 Red and Black

2024-07-15 19:49:08   221人阅读

可重复路径搜索，不需要回溯

这应该也属于很简单很经典的DFS题目


和前面的小狗闯迷宫的题目(HDU 1010 Tempter of the Bone)对比，只能走一条路的题目，是需要回溯的。

原因很简单，寻路失败就需要把迷宫恢复成搜索前的状态

 

吐槽一下我的失误，一看到矩阵我就以为第一个数代表行数，第二个数代表列数

所以读题要仔细，认真审题！

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 8 char map[23][23]; 9 int m, n, Sx, Sy, cnt;10 11 void DFS(int x, int y)12 {13     map[x][y] = ‘#‘;14     for(int i = 0; i < 4; ++i)15     {16         int xx = x + dir[i][0];17         int yy = y + dir[i][1];18         if(xx>=0 && xx<m && yy>=0 && yy<n19             && map[xx][yy] == ‘.‘)20         {21             ++cnt;22             map[xx][yy] = ‘#‘;23             DFS(xx, yy);24         }25     }26 }27 28 int main(void)29 {30     #ifdef LOCAL31         freopen("1312in.txt", "r", stdin);32     #endif33 34     while(scanf("%d%d", &n, &m) == 2)35     {36         if(m == 0 && n == 0)37             break;38         int i, j;39         getchar();40         for(i = 0; i < m; ++i)41         {42             for(j = 0; j < n; ++j)43             {44                 scanf("%c", &map[i][j]);45                 if(map[i][j] == ‘@‘)46                 {47                     Sx = i;48                     Sy = j;49                 }50             }51             getchar();52         }53         map[Sx][Sy] = ‘#‘;54         cnt = 1;55         DFS(Sx, Sy);56         printf("%d\n", cnt);57     }58     return 0;59 }
代码君

 


联系
我们