Uva--572 Oil Deposits(dfs)-526互联

记录
00:22 2023-5-22

https://onlinejudge.org/external/5/p572.pdf

reference:《算法竞赛入门经典第二版》例题6-12

八连块，标准的dfs。
学到的点:使用ind标记连通分量，这个可能有题会用到。

#include<cstdio>
#include<cstring>
#define MAX_N 1024
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;

int result = 0;
char pic[MAX_N][MAX_N];
int ind = 0;
int idx[MAX_N][MAX_N];
int m, n;

void dfs(int x, int y, int ind) {
    if(idx[x][y] > 0 || pic[x][y] != '@') return;
    idx[x][y] = ind;
    for(int dx = -1; dx <= 1; dx++) {
        for(int dy = -1; dy <= 1; dy++) {
            if(dx == 0 && dy == 0) continue;
            else {
                int new_x = x + dx, new_y = y + dy;
                if(0 <= new_x && new_x < m && 0 <= new_y && new_y < n) dfs(new_x, new_y, ind);
            }
        }
    }
}

void dfs1(int x, int y, int ind) {
    if(idx[x][y] > 0) return;
    idx[x][y] = ind;
    for(int dx = -1; dx <= 1; dx++) {
        for(int dy = -1; dy <= 1; dy++) {
            if(dx == 0 && dy == 0) continue;
            else {
                int new_x = x + dx, new_y = y + dy;
                if(0 <= new_x && new_x < m && 0 <= new_y && new_y < n && pic[x][y] == '@') dfs(new_x, new_y, ind);
            }
        }
    }
}


int main () {
  while(scanf("%d%d", &m, &n) == 2 && m && n) {
    ind = 0;
    for(int i = 0; i < m; i++) scanf("%s", pic[i]);
    memset(idx, 0, sizeof(idx));
    for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
        if(idx[i][j] == 0 && pic[i][j] == '@') dfs(i, j, ++ind);
    printf("%d\n", ind);
  }
  return 0;
}