ZeroJudge C129: Oil Deposits

UVa 00572 – Oil Deposits

There is an oil company responsible for exploring the oil content underneath a certain piece of land. The land is rectangular and has been divided into many small pieces for convenience in exploration. Then, instruments are used to explore each small piece. A small piece containing oil is called a pocket. If two pockets are adjacent, then they belong to the same oil deposit. (The definition of adjacency is the same as that in the game of Minesweeper; please refer to the sample input and sample output.)

Your task is to determine how many different oil deposits are contained within this piece of land.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF inputs: each set of data starts with two integers, M and N. M represents the number of rows in the land, and N represents the number of columns. The subsequent M lines represent the exploration content of the land. "@" denotes a pocket containing oil, while "*" denotes a pocket without oil. When M = 0 and N = 0, it indicates the end of the input.For each set of test data, output the number of oil deposits.
1 1
*
3 5
@@*
@
@@*
1 8
@@***@
5 5
**@ *@@*@ *@@
@@@@ @@*@
0 0		0
1
2
2
ZeroJudge C129 範例測資

Thought Process

After collecting the data, iterate through each character one by one. If the current character represents an oil deposit, run a Breadth-First Search (BFS). During BFS, explore in all eight directions: up, down, left, right, upper-right, lower-right, upper-left, and lower-left, ensuring not visit the same point twice. You can declare a map to keep track of visited points. It's important to note that this map can be a global variable so that after BFS finishes, if a point has already been visited, BFS won't be initiated again. Increment the answer every time a BFS is completed.

Sample Code－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
Tags

Related Posts

Comments