阅读 6

Regions Cut By Slashes——LeetCode

题目描述

思想

1、将输入的N*N的grid转化为(N*3)*(n*3)的grid_net,且初始化为0,并且遍历题目所给的grid,将"/"记录在生成的grid_net中为右上角到左下角的3个1,将"\"记录在生成的grid_net中为左上角到右下角的3个1

2、采用dfs进行遍历,将某一块全为0的区域的值改为1,并记录一次dfs为分块的区域数

3、直到整个区域遍历完成,不存在grid_net[i][j] == 0的情况

代码实现

class Solution {
    public int regionsBySlashes(String[] grid) {
        int[][] grid_net =new int[grid.length*3][grid.length*3];
        
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid.length; j++){
                // System.out.println(grid[i].substring(j,j+1));
                if(grid[i].substring(j,j+1).equals("/")){
                    grid_net[i*3][j*3+2] = 1;
                    grid_net[i*3+1][j*3+1] = 1;
                    grid_net[i*3+2][j*3] = 1;
                }else if(grid[i].substring(j,j+1).equals("\\")){
                    grid_net[i*3][j*3] = 1;
                    grid_net[i*3+1][j*3+1] = 1;
                    grid_net[i*3+2][j*3+2] = 1;
                }
            }
        }
        int res = 0;
        
//         for(int m = 0; m < grid_net.length; m++){
//             for(int n = 0;n < grid_net.length; n++){
//                 System.out.print(grid_net[m][n]);
                
//             }
//             System.out.println("");
//         }
        
        
        for(int m = 0; m < grid_net.length; m++){
            for(int n = 0;n < grid_net.length; n++){
                if(grid_net[m][n] == 0){
                    dfs(grid_net,m,n);
                    res++;
                }
            }
        }
        return res;
    }
    
    public void dfs(int[][] grid,int i,int j){
        if(i >= 0 && j >= 0 && i < grid.length && j < grid.length && grid[i][j] == 0){
            grid[i][j] = 1;
            dfs(grid,i-1,j);
            dfs(grid,i+1,j);
            dfs(grid,i,j-1);
            dfs(grid,i,j+1);
        }
    }
}
复制代码
关注下面的标签,发现更多相似文章
评论