X X 0 00 X X 00 0 X 01 0 0 0
TheXcharacters indicate the largest connected component, as per the given definition. There are five cells in this component.
思路分析：这题是Hackerrank一次的比赛题目，也是G公司一次面试中出现的面试原题。要在一个矩阵中找到最大的连通区域。基本可以用DFS搜索解决，在每个位置重启搜索找连通区域，一共有8个方向/分支，，贪心保留最大cell数目。用visited标记数组记录已经count过的位置进行剪枝加速。是一道中规中矩的考察DFS/BFS搜索的题目。
AC Code
import java.io.*;import java.util.*;import java.text.*;import java.math.*;import java.util.regex.*;public class Solution {static int[][] actionCosts = {{1, 0}, {-1, 0}, {0, 1}, {0, -1},{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};static int cellCounter = 0;public static void main(String[] args) throws NumberFormatException, IOException {/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */DataInputStream in = new DataInputStream(new BufferedInputStream(System.in)); int m = Integer.valueOf(in.readLine());int n = Integer.valueOf(in.readLine());int [][] matrix = new int [m][n];for(int i = 0; i < m; i++){String line = in.readLine();for(int j = 0; j < n; j++){matrix[i][j] = Integer.valueOf(line.split(" ")[j]);}}int maxNum = findMaxConnectedCellNum(matrix, m, n);System.out.println(maxNum);}private static int findMaxConnectedCellNum(int[][] matrix, int m, int n) {// TODO Auto-generated method stubint [][] 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 stubif(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);}}}
生活不会永远都困难;祝你爱情蜜甜，事业大进步
