ZeroJudge C129: Oil Deposits

同題：UVa 00572 – Oil Deposits

有一家石油公司負責探勘某塊地底下的石油含量，這塊地是矩行的，並且為了探勘的方便被切割為許多小塊。然後使用儀器對每個小塊去探勘。含有石油的小塊稱為一個 pocket。假如兩個 pocket 相連，則這兩個 pocket 屬於同一個 oil deposit。（所謂相連的定義與踩地雷遊戲中的定義相同，請參考 sample input、sample output）

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

範例測資

範例輸入範例輸出
EOF 輸入，每組資料的第一行有 2 個整數 M 和 N。M 代表這塊地的列數，N 代表這塊地的行數 (1 <= M、N <= 100)。接下來的 M 行就是這塊地探勘的內容。「@」代表此小塊含石油，「*」代表此小塊不含石油。M = 0、N = 0 代表輸入結束。對每組測試資料輸出 oil deposit 的數目。
1 1
*
3 5
@@*
@
@@*
1 8
@@***@
5 5
**@ *@@*@ *@@
@@@@ @@*@
0 0		0
1
2
2
ZeroJudge C129 範例測資

解題思路

收完資料之後一個一個字元做判斷，如果目前字元有石油，就跑 BFS。跑 BFS 的時候要跑「上、下、左、右、右上、右下、左上、左下」八個方位，並且不能跑到重複的點。可以宣告一個 Map 來存哪些點已經走過了，要注意的是這個 Map 可以設成全域變數，這樣子 BFS 結束後跑到已經走過的點就不會再進 BFS。每當一個 BFS 結束時就將答案+1。

範例程式碼－ZeroJudge C129: Oil Deposits

#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<string>v;
int N, M, ans = 0, loc[8][2] ={{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, 1}, {1, 1}, {-1, -1}, {1, -1}};
map<pair<int, int>, int>MAP;

pair<int, int>axis(int a, int b)
{
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

void BFS(vector<pair<int, int>>start)
{
    if (start.size() == 0)
    {
        ans++;
        return;
    }
    vector<pair<int, int>>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        MAP[start[i]]++;
        int y = start[i].first, x = start[i].second;
        for (int j = 0; j<8; j++)
        {
            int yy = y + loc[j][0], xx = x + loc[j][1];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M && MAP[axis(yy, xx)] == 0 && v[yy][xx] == '@')
            {
                newStart.push_back(axis(yy, xx));
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N >> M && N != 0 && M != 0)
    {
        v.clear();
        ans = 0;
        MAP.clear();
        for (int i = 0; i<N; i++)
        {
            string str;
            cin >> str;
            v.push_back(str);
        }
        for (int i = 0; i<N; i++)
        {
            for (int j = 0; j<M; j++)
            {
                if (v[i][j] == '@' && MAP[axis(i, j)] == 0)
                {
                    vector<pair<int, int>>start;
                    start.push_back(axis(i, j));
                    BFS(start);
                }
            }
        }
        cout << ans << "\n";
    }
}

//ZeroJudge C129
//Dr. SeanXD
標籤

相關文章

發佈留言