【算法积累】Oil Deposits（DFS&BFS）

淩亂°似流年 2022-11-11 13:17 126阅读 0赞

# 题目描述 #

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

**Input**  
The input file contains one or more grids. Each grid begins with a line containing  m m m and  n n n, the number of rows and columns in the grid, separated by a single space. If  m = 0 m=0 m=0 it signals the end of the input; otherwise  1 ≤ m ≤ 100 1≤m≤100 1≤m≤100 and  1 ≤ n ≤ 100 1≤n≤100 1≤n≤100. Following this are  m m m lines of  n n n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*`, representing the absence of oil, or `@`, representing an oil pocket.

**Output**  
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than  100 100 100 pockets.

**Sample Input**

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

**Sample Output**

0
    1
    2
    2

# 解法1：深度优先搜索 (DFS) #

深度优先搜索的基本思想是尽可能先对纵深方向进行搜索，从油田地图的一点出发，访问该点，然后依次从该点的各个未被访问的相邻点出发深度优先遍历搜索，直至所有和该点相邻的点都被访问到。若地图中还有点未被访问，则另选一个点作为新的出发点，重复上述过程，直至地图中所有点都被访问到。  
首先我们定义一个二维数组，用来记录方向。

int di[8][2] = { 
            { -1, -1},
            { -1, 0},
            { -1, 1},
            { 0, -1},
            { 0, 1},
            { 1, -1},
            { 1, 0},
            { 1, 1}
    };

在进行DFS的时候，我们需要将已经遍历到的点标记为`*`，再依次遍历搜索该点的相邻点，直至所有点都被遍历过。整个过程是一个递归过程，也可以借助栈这种数据结构改写为非递归形式。  
下面给出递归形式的代码。  
语言：C++  
代码：

#include <iostream>
    using namespace std;
    
    int m, n;
    int x_next, y_next;
    char map[105][105];
    int di[8][2] = { 
            { -1, -1},
            { -1, 0},
            { -1, 1},
            { 0, -1},
            { 0, 1},
            { 1, -1},
            { 1, 0},
            { 1, 1}
    };
    
    void dfs(int x, int y) { 
        map[x][y] = '*';
        for (auto & i : di) { 
            x_next = x + i[0];
            y_next = y + i[1];
            if (x_next < 0 || y_next < 0 || x_next >= m || y_next >= n) { 
                continue;
            }
            if (map[x_next][y_next] == '@') { 
                dfs(x_next, y_next);
            }
        }
    }
    
    int main() { 
        while (true) { 
            cin >> m >> n;
            if (m == 0 && n == 0) { 
                break;
            }
            for (int i = 0; i < m; i++) { 
                cin >> map[i];
            }
            int ans = 0;
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (map[i][j] == '@') { 
                        dfs(i, j);
                        ans++;
                    }
                }
            }
            cout << ans << endl;
        }
        return 0;
    }

# 解法2：广度优先搜索 (BFS) #

广度优先搜索的基本思想是从油田地图的一点出发，在访问该点之后依次访问该点的所有未被访问的相邻点，之后按这些相邻点被访问的先后次序依次访问它们的相邻点，直至地图中所有和出发点有路径相通的点都被访问到。若地图中还有点未被访问，则另选一个点作为新的出发点，重复上述过程，直至地图中所有点都被访问到。  
和DFS一样，我们也需要定义一个二维数组`di`记录方向。同样地，我们也需要将已经遍历到的点标记为`*`。  
我们可以借助队列这种数据结构保存已经访问过的点的坐标，利用队列FIFO（first in first out，先进先出）的特点，使得先访问到的点的相邻点在下一轮优先被遍历搜索到。在搜索过程中，每访问一个点就将其进行入队操作，当队首元素出队时，将其未被访问的相邻点入队，每个点入队一次。若队列为空，则一次BFS结束，此时另选一个点作为新的出发点进行下一次BFS，直至所有点都被访问。  
语言：C++  
代码：

#include <iostream>
    #include <queue>
    using namespace std;
    
    int m, n;
    int x_next, y_next;
    char map[105][105];
    int di[8][2] = { 
            { -1, -1},
            { -1, 0},
            { -1, 1},
            { 0, -1},
            { 0, 1},
            { 1, -1},
            { 1, 0},
            { 1, 1}
    };
    
    void bfs(int x, int y) { 
        map[x][y] = '*';
        queue<pair<int, int>> q;
        q.push(pair<int, int>(x, y));
        while (!q.empty()) { 
            pair<int, int> q_front = q.front();
            q.pop();
            for (auto & i : di) { 
                x_next = q_front.first + i[0];
                y_next = q_front.second + i[1];
                if (x_next < 0 || y_next < 0 || x_next >= m || y_next >= n) { 
                    continue;
                }
                if (map[x_next][y_next] == '@') { 
                    q.push(pair<int, int>(x_next, y_next));
                    map[x_next][y_next] = '*';
                }
            }
        }
    }
    
    int main() { 
        while (true) { 
            cin >> m >> n;
            if (m == 0 && n == 0) { 
                break;
            }
            for (int i = 0; i < m; i++) { 
                cin >> map[i];
            }
            int ans = 0;
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (map[i][j] == '@') { 
                        ans++;
                        bfs(i, j);
                    }
                }
            }
            cout << ans << endl;
        }
        return 0;
    }