[leetcode]Regions Cut By Slashes-DFS

心已赠人 2021-09-29 04:58 226阅读 0赞

### Regions Cut By Slashes ###

*  题目
 *  思考
 *  代码（dfs）

# 题目 #

[leetcode入口][leetcode]

# 思考 #

这道题的难点在于把问题抽象为求解连通分量个数的题，并且要知道如何建图

将一个正方形方格分成四个三角形部分记为0，1，2，3，分别对应左边，下边，右边，上边的三角形。

不论是什么输入（暂不考虑边界情况）  
该正方形的1都能与下面的正方形的3连接  
该正方形的2都能与右边的正方形的0连接

**分情况**  
**输入" "：**  
连接0-3 1-2 0-1 2-3

**输入"\\"**  
连接0-1,2-3

**输入"/"**  
连接0-3,1-2

# 代码（dfs） #

class Solution { 
    public:
        void connect(vector<vector<int>> &graph,int a,int b){ 
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        
        void dfs(int i,vector<bool>& visited,vector<vector<int>>& graph){ 
            for(int j=0;j<graph[i].size();j++){ 
                if(!visited[graph[i][j]]){ 
                    visited[graph[i][j]]=true;
                    dfs(graph[i][j],visited,graph);
                }
            }
        }
        
        int regionsBySlashes(vector<string>& grid) { 
            vector<vector<int>> graph(grid.size()*grid.size()*4,vector<int>());
            
            int N=grid.size();
            int n=0;
            int n1=0;
            
            //构造初始的连接
            for(int i=0;i<grid.size();i++){ 
                for(int j=0;j<grid[0].size();j++){ 
                    n=4*(i*N+j);
                    if(i<N-1){ 
                        //当前框编号
                        
                        //当前框下面的框
                        n1=4*((i+1)*N+j);
                        connect(graph,n+1,n1+3);
                    }
                    if(j<N-1){ 
                        //当前框右面的框
                        n1=4*(i*N+j+1);
                        connect(graph,n+2,n1);
                    }
                }
            }
            
            //根据输入构造连接
            for(int i=0;i<grid.size();i++){ 
                for(int j=0;j<grid[0].size();j++){ 
                    //当前框编号
                    n=4*(i*N+j);
                    if(grid[i][j]!='\\'){ 
                        connect(graph,n,n+3);
                        connect(graph,n+1,n+2);
                    }
                    if(grid[i][j]!='/'){ 
                        connect(graph,n,n+1);
                        connect(graph,n+2,n+3);
                    }
                }
            }
            
            vector<bool> visited(4*N*N,0);
            int cnt=0;
            for(int i=0;i<4*N*N;i++){ 
                if(!visited[i]){ 
                    visited[i]=true;
                    dfs(i,visited,graph);
                    cnt++;
                }
            }
            return cnt;
        }
    };

[leetcode]: https://leetcode.com/problems/regions-cut-by-slashes/