现在的位置: 首页 > 综合 > 正文

hdoj 1241 Oil Deposits

2019年07月31日 ⁄ 综合 ⁄ 共 683字 ⁄ 字号 评论关闭

http://acm.hdu.edu.cn/showproblem.php?pid=1241

//题意大致就是将矩形区域中有多少的@组成的区域,*为隔开的符号
//深度优先搜索,向八个方向有@的方向深入搜索,并且将其覆盖为*
#include <iostream>
#include <string>
using namespace std;

char M[101][101];
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int m, n;

void search (int a, int b)
{
 int i;
 if (M[a][b] == '*')
  return ;
 if (a < 0 || b < 0 || a > m || b > n)
  return ;
 if (M[a][b] == '@') {
  M[a][b] = '*';
  for (i = 0; i < 8; i++) {
    search(a + dir[i][0], b + dir[i][1]);
   }
 }
}
int main()
{
 int result;
 int i, j;
 string str;
 while (cin >> m >> n && (n+m)) {
  result = 0;
  memset (M, '*', sizeof(M));
  for (i = 0; i < m; i++) {
   cin >> str;
   for (j = 0; j < n; j++) {
    if (str[j] == '@')
     M[i][j] = '@';
   }
  }
  for (i = 0; i < m; i++) 
   for (j = 0; j < n; j++) {
    if (M[i][j] == '@') {
     search(i, j);
     result ++;
    }
   }
  cout << result << endl;
 }
 return 0;
}

 

【上篇】
【下篇】

抱歉!评论已关闭.