本文共 3520 字，大约阅读时间需要 11 分钟。

The GeoSurvComp geologic survey company specializes in detecting underground oil deposits by analyzing large rectangular grids. The company divides the land into square plots and uses sensors to identify oil pockets, which are plots containing oil. Two adjacent pockets (including diagonally adjacent ones) are considered part of the same oil deposit. Your task is to determine the number of distinct oil deposits in a given grid.

Input Format

The input consists of one or more grids. Each grid starts with a line containing two integers, m and n, representing the number of rows and columns. If m is 0, it indicates the end of the input. Each subsequent line contains n characters, where '*' represents no oil and '@' represents an oil pocket. The input may contain multiple grids, each with its own m and n values.

Sample Input

1 1*3 5*@*@***@***@*@*1 8@@****@*5 5 ****@*@@*@*@**@@@@*@@@**@0 0

Output

The output should be a sequence of numbers, each representing the number of oil deposits in the corresponding grid. For example:

0122

Key Points

• Oil deposits are defined as groups of adjacent oil pockets, where adjacency includes horizontal, vertical, and diagonal connections.
• Each oil deposit cannot contain more than 100 pockets.
• The task is computationally intensive, as it involves analyzing grids of up to 100x100 size.

Approach

To solve this problem, a Depth-First Search (DFS) algorithm is typically used to explore and mark all connected pockets of oil. Here’s a step-by-step breakdown of the approach:

Solution Code

#include 
   
    
#include 
    
     
using namespace std;
int main() {
    int m, n;
    vector
     
      
       > grid(100+1, vector
       
        (100+1));
    int count = 0;
    
    while (true) {
        cin >> m >> n;
        if (m == 0) break;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                grid[i][j] = cin.get();
            }
        }
        
        vector
        
         
          > oilDeposits; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '@') { bool visited[m][n] = {false}; queue
          
           
            > q; q.push({i, j}); visited[i][j] = true; int currentDeposit = 0; while (!q.empty()) { auto current = q.front(); q.pop(); for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { if (dx == 0 && dy == 0) continue; int x = current.first + dx; int y = current.second + dy; if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && grid[x][y] == '@') { visited[x][y] = true; q.push({x, y}); } } } } oilDeposits.push_back({i, j}); ++count; } } } cout << count; if (m == 0) break; } return 0; }
           
          
         
        
       
      
     
    
   

Explanation

The code reads multiple grids and counts the number of oil deposits in each grid. For each grid, it uses a DFS algorithm to explore all connected oil pockets, marking them as visited to avoid recounting. Each new DFS initiation corresponds to a new oil deposit. The result is printed as a sequence of numbers, each representing the count of oil deposits in the corresponding grid.

This approach ensures that all adjacent pockets (including diagonally adjacent ones) are counted correctly, and it efficiently handles grids of up to 100x100 size.

转载地址：http://stsfk.baihongyu.com/