首页 > 代码库 > HDU 1241 Oil Deposits

HDU 1241 Oil Deposits

2024-07-15 19:48:38   218人阅读

很简单很经典的DFS题目

题意：

‘@‘代表一块油田，在以它为中心的九宫格里的‘@‘，也算同在一块油田，问所给矩阵中有多少块油田

思路：

遍历地图中的每一个格子，如果遇到‘@‘，则DFS，将这块变为‘*‘，然后八个方向继续DFS

这样整个搜索完毕以后，这个map就全部变为‘*‘了

 

第一次居然忘了做数组越界检测，结果还AC了，不过以后DFS千万千万要记得这个！

=_=!! 

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 char map[103][103]; 8 int dir[8][2] = {{0, 1},{0, -1},{1, 0}, {-1, 0},{1, 1}, {1, -1},{-1, 1},{-1, -1}}; 9 int m, n;10 11 void DFS(int x, int y)12 {13     map[x][y] = ‘*‘;14     for(int i = 0; i < 8; ++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             map[xx][yy] = ‘*‘;22             DFS(xx, yy);23         }24     }25 }26 27 int main(void)28 {29     #ifdef LOCAL30         freopen("1241in.txt", "r", stdin);31     #endif32 33     while(scanf("%d%d", &m, &n) == 2)34     {35         if(m == 0 && n == 0)36             break;37         for(int i = 0; i < m; ++i)38             scanf("%s", map[i]);39         int cnt = 0;40         for(int i = 0; i < m; ++i)41             for(int j = 0; j < n; ++j)42             {43                 if(map[i][j] == ‘@‘)44                 {45                     ++cnt;46                     DFS(i, j);47                 }48             }49 50         printf("%d\n", cnt);51     }52     return 0;53 }
代码君

 


联系
我们