Hackerrank Connected Cell in a Grid - Coding for Dreams - 博客频道 - CSDN.NET
You are given a matrix withm rows and n columns of cells, each of which contains either 1 or 0 . Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. The connected and filled (i.e. cells that contain a 1 ) cells form aregion. There may be several regions in the matrix. Find the number of cells in the largest region in the matrix.
要在一个矩阵中找到最大的连通区域。基本可以用DFS搜索解决，在每个位置重启搜索找连通区域，一共有8个方向/分支，贪心保留最大cell数目。用visited标记数组记录已经count过的位置进行剪枝加速
def solve(self, cipher):
m, n, mat = cipher
visited = [[False for _ in xrange(n)] for _ in xrange(m)]
for i in xrange(m):
for j in xrange(n):
if not visited[i][j] and mat[i][j]==1:
self.cur_area = 0
self.dfs(visited, mat, i, j, m, n)
return self.max
def dfs(self, visited, mat, i, j, m, n):
visited[i][j] = True
self.cur_area += 1
self.max = max(self.max, self.cur_area)
for dir in self.dirs:
i1 = i+dir[0]
j1 = j+dir[1]
if 0<=i1<m and 0<=j1<n and not visited[i1][j1] and mat[i1][j1]==1:
self.dfs(visited, mat, i1, j1, m, n)
Read full article from Hackerrank Connected Cell in a Grid - Coding for Dreams - 博客频道 - CSDN.NET
You are given a matrix with
要在一个矩阵中找到最大的连通区域。基本可以用DFS搜索解决，在每个位置重启搜索找连通区域，一共有8个方向/分支，贪心保留最大cell数目。用visited标记数组记录已经count过的位置进行剪枝加速
private static int findMaxConnectedCellNum(int[][] matrix, int m, int n) {
// TODO Auto-generated method stub
int [][] visited = new int[m][n];
int maxNum = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
dfs(matrix, visited, i, j, m, n);
if(cellCounter > maxNum) maxNum = cellCounter;
cellCounter = 0;
}
}
return maxNum;
}
private static void dfs(int[][] matrix, int[][] visited, int i, int j,
int m, int n) {
// TODO Auto-generated method stub
if(i < 0 || i >= m || j < 0 || j >= n){
return;
}
if(visited[i][j] == 1 || matrix[i][j] == 0) return;
cellCounter++;
visited[i][j] = 1;
for(int di = 0; di < 8; di++){
dfs(matrix, visited, i + actionCosts[di][0], j + actionCosts[di][1], m, n);
}
}
https://github.com/algorhythms/HackerRankAlgorithms/blob/master/Connected%20Cell%20in%20a%20Grid.pydef solve(self, cipher):
m, n, mat = cipher
visited = [[False for _ in xrange(n)] for _ in xrange(m)]
for i in xrange(m):
for j in xrange(n):
if not visited[i][j] and mat[i][j]==1:
self.cur_area = 0
self.dfs(visited, mat, i, j, m, n)
return self.max
def dfs(self, visited, mat, i, j, m, n):
visited[i][j] = True
self.cur_area += 1
self.max = max(self.max, self.cur_area)
for dir in self.dirs:
i1 = i+dir[0]
j1 = j+dir[1]
if 0<=i1<m and 0<=j1<n and not visited[i1][j1] and mat[i1][j1]==1:
self.dfs(visited, mat, i1, j1, m, n)
Read full article from Hackerrank Connected Cell in a Grid - Coding for Dreams - 博客频道 - CSDN.NET
