#UVa:572-Oil Deposits

灆洢 2014-12-29 16:25:44

在計算的時候利用標記將相鄰的地方全部標示起來即可正確計算其數量。

C++(0.026)

/*******************************************************/
/* UVa 572 Oil Deposits                                */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2014/12/29                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

const int MAX_MAP_LIMIT = 100;

void visit(bool isVisited[][MAX_MAP_LIMIT+5], 
           char map[][MAX_MAP_LIMIT+5],
           int i, int j ){
  if( map[i][j] == '@' && !isVisited[i][j] ){
    isVisited[i][j] = true;
    visit( isVisited, map, i-1, j );
    visit( isVisited, map, i+1, j );
    visit( isVisited, map, i, j+1 );
    visit( isVisited, map, i, j-1 );
    visit( isVisited, map, i+1, j-1 );
    visit( isVisited, map, i+1, j+1 );
    visit( isVisited, map, i-1, j-1 );
    visit( isVisited, map, i-1, j+1 );
  }

}

int main(){
  int m, n;
  while( scanf("%d%d", &m, &n) != EOF && m > 0 ){
    char map[MAX_MAP_LIMIT+5][MAX_MAP_LIMIT+5] = {0};
    gets(map[0]); // for '\n'
    for( int i = 1 ; i <= m ; ++i ){
      gets(map[i]+1);
    }

    bool isVisited[MAX_MAP_LIMIT+5][MAX_MAP_LIMIT+5] = {0};
    int oilCount = 0;
    for( int i = 1 ; i <= m ; ++i ){
      for( int j = 1 ; j <= n ; ++j ){
        if( map[i][j] == '@' && !isVisited[i][j] ){
          ++oilCount;
          visit( isVisited, map, i, j );
        }
      }
    }

    printf("%d\n", oilCount);
  }
  return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料