【DFS】个人练习-Leetcode-LCS 03. 主题空间

题目链接：https://leetcode.cn/problems/YesdPw/description/

题目大意：二位字符数组grid[][]，0代表走廊，其他字符代表某种type的房间。上下左右连续的同type的房间被视为同一块区域。grid[][]边缘的房间也视为和走廊相接（相当于最外层包了一圈0）。求不和0接触的最大的区域面积。

思路：主要还是DFS，但具体怎么DFS没想太明白，写得磕磕绊绊，最后还是看了题解如何处理妥当。唉，纸上得来终觉浅，绝知此事要躬行。

外层循环（DFS入口），使用一个pair<int, bool>来作为本块区域的结果，first代表其面积，second代表这块区域是否和0接触。

        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] != '6' && grid[i][j] != '0') {
                    pair<int, bool> p = make_pair(0, true);
                    DFS(grid, i, j, p);
                    if (p.second)
                        res = max(res, p.first);
                }
            }
        }

DFS本体，将区域标记为6表示已经访问过。探索四个邻居，如果【越界】【是走廊=0】那么这块区域的面积就无效了，second置为false；
如果【没越界】并且【邻居房间种类和原位相同（这也保证了未访问，因为!=6）】，那么继续DFS

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    void DFS(vector<string>& grid, int x, int y, pair<int, bool>& p) {
        char type = grid[x][y];
        grid[x][y] = '6';
        p.first++;
        for (int i = 0; i < 4; i++) {
            int a = x+dx[i], b = y+dy[i];
            if (a < 0 || b < 0 || a >= grid.size() || b >= grid[0].size() || grid[a][b] == '0') {
                p.second = false;
            }
            if (a >= 0 && b >= 0 && a < grid.size() && b < grid[0].size() && grid[a][b] == type) {
                DFS(grid, a, b, p);
            }
        }
    }

完整代码

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    void DFS(vector<string>& grid, int x, int y, pair<int, bool>& p) {
        char type = grid[x][y];
        grid[x][y] = '6';
        p.first++;
        for (int i = 0; i < 4; i++) {
            int a = x+dx[i], b = y+dy[i];
            if (a < 0 || b < 0 || a >= grid.size() || b >= grid[0].size() || grid[a][b] == '0') {
                p.second = false;
            }
            if (a >= 0 && b >= 0 && a < grid.size() && b < grid[0].size() && grid[a][b] == type) {
                DFS(grid, a, b, p);
            }
        }
    }


    int largestArea(vector<string>& grid) {
        int res = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] != '6' && grid[i][j] != '0') {
                    pair<int, bool> p = make_pair(0, true);
                    DFS(grid, i, j, p);
                    if (p.second)
                        res = max(res, p.first);
                }
            }
        }
        return res;
    }
};