主题空间

LCS 03. 主题空间

难度中等3

「以扣会友」线下活动所在场地由若干主题空间与走廊组成，场地的地图记作由一维字符串型数组 grid，字符串中仅包含 "0"～"5" 这 6 个字符。地图上每一个字符代表面积为 1 的区域，其中 "0" 表示走廊，其他字符表示主题空间。相同且连续（连续指上、下、左、右四个方向连接）的字符组成同一个主题空间。

假如整个 grid 区域的外侧均为走廊。请问，不与走廊直接相邻的主题空间的最大面积是多少？如果不存在这样的空间请返回 0。

示例 1:

输入：grid = ["110","231","221"]

输出：1

解释：4 个主题空间中，只有 1 个不与走廊相邻，面积为 1。

示例 2:

输入：grid = ["11111100000","21243101111","21224101221","11111101111"]

输出：3

解释：8 个主题空间中，有 5 个不与走廊相邻，面积分别为 3、1、1、1、2，最大面积为 3。

提示：

• 1 <= grid.length <= 500
• 1 <= grid[i].length <= 500
• grid[i][j] 仅可能是 "0"～"5"

DFS

class Solution {
    public int largestArea(String[] grid) {
        m = grid.length;
        n = grid[0].length();
        visited = new boolean [m][n];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!visited[i][j]){
                    cnt = 0;
                    flag = true;
                    last = grid[i].charAt(j);
                    dfs(grid,i,j);
                    if(flag)max = Math.max(cnt,max);
                }
            }
        }
        return max;
    }
    int max = 0;
    boolean[][]visited = null;
    int m=0,n=0;
    char last = '6';
    int cnt = 0;
    boolean flag = true;

    public void dfs(String[]grid,int x,int y){
        if(x<0||x>=m||y<0||y>=n||visited[x][y])return;
        
        if(last=='0')flag =false;
        if(grid[x].charAt(y)==last){
            visited[x][y] = true;
            cnt++;
            if(x-1<0||x+1>=m||y-1<0||y+1>=n||
            grid[x+1].charAt(y)=='0'||grid[x].charAt(y+1)=='0'||
            grid[x-1].charAt(y)=='0'||grid[x].charAt(y-1)=='0'){
                flag=false;
            }
            dfs(grid,x+1,y);
            dfs(grid,x,y+1);
            dfs(grid,x-1,y);
            dfs(grid,x,y-1);
        }
    }
}

赏

谢谢你请我吃糖果

微信