UVA 00572 - Oil Deposits

解題觀念

BFS & DFS

可以參考我的課程簡報：BFS & DFS
關於 BFS 的基本觀念可以參考我的這篇文章：Algorithm - BFS
關於 DFS 的基本觀念可以參考我的這篇文章：Algorithm - DFS

題目敘述

有家石油公司負責探勘某塊地底下的石油含量，這塊地是矩行的
含有石油的一小塊地稱作一個 pocket，假如兩個 pocket 相連，則這兩個 pocket 屬於同一個 oil deposit

你的任務就是要找出這塊地包含幾個不同的 oil deposit

Input

輸入包含好幾組資料，每組資料的第一行有 2 個整數 m, n
m 代表這塊地的列數，n代表這塊地的行數（1 <= m, n <= 100）

接下來的 m 行是這塊地探勘的內容
@ 代表此小塊含石油，*代表此小塊不含石油

當 m = 0 && n = 0 則輸入結束

// Sample Input
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Output

對每組測試資料輸出 oil deposit 的數目

// Sample Output
0
1
2
2

Solution Code

#include<bits/stdc++.h>
using namespace std;

int m, n;
int x_now, y_now, x_next, y_next;

int ans;
char oil[100][100];

int row[] = { 1, 1, 1, 0, -1, -1, -1, 0 };
int column[] = { -1, 0, 1, 1, 1, 0, -1, -1 };

void dfs( int x_now, int y_now ){

    for( int j = 0; j < 8; j++ ){

        x_next = x_now + row[j];
        y_next = y_now + column[j];

        if( x_next < m && y_next < n && x_next >= 0 && y_next >= 0 && oil[ x_next ][ y_next ] == '@' ){

            // 此點已找過 就把他改成普通地板
            oil[ x_next ][ y_next ] = '*';
            dfs( x_next, y_next );

        }
    }
    
    return;
}

int main(){

    while( cin >> m >> n && m && n ){

        memset( oil, '0', sizeof(oil) );
        ans = 0;

        for( int i = 0; i < m; i++ ){
            for( int j = 0; j < n; j++ ){
                cin >> oil[i][j];          
            }
        }

        for( int i = 0; i < m; i++ ){
            for( int j = 0; j < n; j++ ){

                if( oil[i][j] == '@' ){
                   ans++;
                   bfs( i, j );
                }
            }
        }
        cout << ans << endl;
    }
}