cpp 解法, 执行用时: 220 ms, 内存消耗: 15.2 MB, 提交时间: 2023-10-10 15:49:31

class Solution {
public:
    int largestArea(vector<string>& grid){
        int n=grid.size(),res=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<grid[i].size();++j){
                int flag=1,count=0;
                if(grid[i][j]>='1'&&grid[i][j]<='5'){
                    helper(grid,i,j,flag,grid[i][j],count);
                    if(flag) res=max(count,res);
                }   
            }
        }
        return res;
    }
    void helper(vector<string>& grid,int x,int y,int& flag,char ch,int& count){
        if(x<0||x>=grid.size()||y<0||y>=grid[x].size()||grid[x][y]=='0'){
            flag=0;return;
        }
        if(grid[x][y]!=ch) return;
        grid[x][y]='6';
        count++;
        helper(grid,x+1,y,flag,ch,count);
        helper(grid,x-1,y,flag,ch,count);
        helper(grid,x,y+1,flag,ch,count);
        helper(grid,x,y-1,flag,ch,count);
    }
                   
};

java 解法, 执行用时: 59 ms, 内存消耗: 43.5 MB, 提交时间: 2023-10-10 15:48:54

class Solution {
    public int largestArea(String[] grid) {
        int n = grid.length;
        int m = grid[0].length();
        // 构造，多加两行两列避免边界问题
        int[][] vals = new int[n+2][m+2];
        for(int i=1;i<n+1;i++){
            for(int j=1;j<m+1;j++){
                vals[i][j] = grid[i-1].charAt(j-1) - '0';
            }
        }
        int maxSize = 0;
        // dfs+剪枝
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(vals[i][j] <= 0){
                    continue;
                }
                maxSize = Math.max(maxSize, getSize(vals, i, j, Math.abs(vals[i][j])));
            }
        }
        return maxSize;
    }

    private int getSize(int[][] vals, int i, int j, int val){
        int size = 1;
        boolean isNearZero = vals[i][j] == 0 || vals[i-1][j] == 0 || vals[i+1][j] == 0 || vals[i][j-1] == 0 || vals[i][j+1] == 0;
        vals[i][j] = 0 - vals[i][j]; // 此处直接取反，标识该位置已经遍历过
        int l = 0, r = 0, u = 0, d = 0;
        if(vals[i-1][j] == val){
            l = getSize(vals,  i-1, j, val);
        }
        if(vals[i+1][j] == val){
            r = getSize(vals,  i+1, j, val);
        }
        if(vals[i][j-1] == val){
            u = getSize(vals,  i, j-1, val);
        }
        if(vals[i][j+1] == val){
            d = getSize(vals,  i, j+1, val);
        }
        
        if(isNearZero || l == -1 || r == -1 || u == -1 || d == -1){
            return -1;
        }
        return size + l + r + u + d;
    }
}

java 解法, 执行用时: 102 ms, 内存消耗: 44.4 MB, 提交时间: 2023-10-10 15:48:40

class Solution {
	public int largestArea(String[] grid) {
		int m = grid.length, n = grid[0].length();
		UnionFindXY union = new UnionFindXY(m, n);
		union.init(grid);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				union.union2(i, j);
			}
		}
		return union.ans();
	}

	class UnionFindXY {
		int[] roots;
		int[] sizes;
		int[] stack;
		int size;
		int m, n;
		//
		boolean[] isWay;
		boolean[] next;
		char[][] cs;

		public UnionFindXY(int m, int n) {
			size = m * n;
			this.m = m;
			this.n = n;
			roots = new int[size];
			sizes = new int[size];
			for (int i = 0; i < size; i++) {
				roots[i] = i;
				sizes[i] = 1;
			}
			stack = new int[size];
		}

		public void union2(int i, int j) {
			this.union(i - 1, j, i, j);
			this.union(i, j - 1, i, j);
		}

		public int ans() {
			int ans = 0;
			for (int i = 0; i < size; i++) {
				if (this.sizes[i] > 0 && !this.next[i]) {
					ans = Math.max(ans, this.sizes[i]);
				}
			}
			return ans;
		}

		public void init(String[] grid) {
			cs = new char[m][n];
			for (int i = 0; i < m; i++) {
				cs[i] = grid[i].toCharArray();
			}
			this.isWay = new boolean[size];
			this.next = new boolean[size];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					char c = cs[i][j];
					int index = this.index(i, j);
					if (c == '0') {
						this.isWay[index] = true;
						this.next[index] = true;
						this.sizes[index] = 0;
					} else {
						if (this.next(i, j, cs)) {
							this.next[index] = true;
						}
					}
				}
			}
		}

		int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

		private boolean next(int x, int y, char[][] cs) {
			for (int i = 0; i < 8; i += 2) {
				int nextx = x + d[i], nexty = y + d[i + 1];
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
					if (cs[nextx][nexty] == '0') {
						return true;
					}
				} else {
					return true;
				}
			}
			return false;
		}

		public int findRoot(int id) {
			int root = 0, p = 0;
			while ((root = roots[id]) != id) {
				stack[p++] = id;
				id = root;
			}
			while (p > 0) {
				roots[stack[--p]] = root;
			}
			return root;
		}

		public boolean isSameSet(int id1, int id2) {
			return findRoot(id1) == findRoot(id2);
		}

		public void union(int id1, int id2) {
			int p1 = this.findRoot(id1);
			int p2 = this.findRoot(id2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.roots[p1] = p2;
					this.sizes[p2] = size1 + size2;
					this.sizes[p1] = 0;
					this.next[p2] = this.next[p1] || this.next[p2];
				} else {
					this.roots[p2] = p1;
					this.sizes[p1] = size1 + size2;
					this.sizes[p2] = 0;
					this.next[p1] = this.next[p1] || this.next[p2];
				}
			}
		}

		public boolean isSameSet(int x1, int y1, int x2, int y2) {
			int id1 = this.index(x1, y1);
			int id2 = this.index(x2, y2);
			return this.isSameSet(id1, id2);
		}

		public void union(int x1, int y1, int x2, int y2) {
			if (x1 < 0 || y1 < 0) {
				return;
			}
			int id1 = this.index(x1, y1);
			int id2 = this.index(x2, y2);
			if (cs[x1][y1] == cs[x2][y2] && cs[x1][y1] != '0') {
				this.union(id1, id2);
			}
			if (cs[x1][y1] == '0') {
				this.next[id2] = true;
				this.next[this.findRoot(id2)] = true;
			}
			if (cs[x2][y2] == '0') {
				this.next[id1] = true;
				this.next[this.findRoot(id1)] = true;
			}
		}

		public int index(int i, int j) {
			return i * n + j;
		}
	}
}

golang 解法, 执行用时: 92 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-10 15:47:49

func largestArea(grid []string) int {
	m, n := len(grid), len(grid[0])
	visited := make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	var dirList = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	var dfs func(int, int, byte) (bool, int)
	dfs = func(i, j int, c byte) (bool, int) {
		if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0' {
			return true, 0
		}
		
		if grid[i][j] != c || visited[i][j] {
			return false, 0
		}
		visited[i][j] = true
		area := 1
		reachEdge := false
		for _, dir := range dirList {
			x, y := i+dir[0], j+dir[1]
			reach, sum := dfs(x, y, grid[i][j])
			reachEdge = reachEdge || reach
			area += sum
		}
		return reachEdge, area
	}

	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] != '0' || visited[i][j] {
				reach, sum := dfs(i, j, grid[i][j])
				if reach {
					continue
				}
				ans = max(ans, sum)
			}
		}
	}
	return ans
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

golang 解法, 执行用时: 580 ms, 内存消耗: 21.1 MB, 提交时间: 2023-10-10 15:47:27

func largestArea(grid []string) int {
    m,n:=len(grid),len(grid[0])
    var isEdge=false
    var visited=map[node]bool{}
    var dfs func(cur node, val byte)int
    dfs=func(cur node, val byte)int{
        if !isInGrid(cur.x,cur.y,m,n){
            isEdge=true
            return 0
        }
        if  visited[cur]{
            return 0
        }
        if grid[cur.x][cur.y] !=val{
            if grid[cur.x][cur.y] =='0'{
                isEdge=true
            }
            return 0
        }
        visited[cur]=true
        res:=0
        for _,d :=range dirs{
            nx,ny:=cur.x+d[0],cur.y+d[1]
            res+=dfs(node{nx,ny},val)
        }
        return 1+res
    }
    
    ans:=0
    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if grid[i][j]=='0'||visited[node{i,j}]{
                continue
            }
            isEdge=false
            res:=dfs(node{i,j},grid[i][j])
           // fmt.Printf("val=%s\t res=%d\t isEdge=%t\n",string(grid[i][j]),res,isEdge)
            if !isEdge{
                ans=max(ans,res)
            }
        }
    }
    return ans
}

var dirs= [][]int{{0,1},{1,0},{0,-1},{-1,0}}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
func isInGrid(x,y,m,n int)bool{
    return 0<=x && x<m && 0<=y && y<n
}
type node struct{
    x,y int
}

python3 解法, 执行用时: 2576 ms, 内存消耗: 18.7 MB, 提交时间: 2023-10-10 15:46:55

class Solution:
    def largestArea(self, grid: List[str]) -> int:
        
        def dfs(grid, r, c, sig):
            if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
                return -1
            if grid[r][c] == '0':
                return -1
            if grid[r][c] != sig:
                return 0

            grid[r][c] = '-1'
            
            a1 = dfs(grid, r - 1, c, sig)
            a2 = dfs(grid, r + 1, c, sig)
            a3 = dfs(grid, r, c - 1, sig)
            a4 = dfs(grid, r, c + 1, sig)

            if a1 != -1 and a2 != -1 and a3 != -1 and a4 != -1: 
                return 1 + a1 + a2 + a3 + a4
            else:
                return -1
        
        grid = [list(grid[idx]) for idx in range(len(grid))]
        
        ans = 0
        nrow, ncol = len(grid), len(grid[0])
        for irow in range(nrow):
            for icol in range(ncol):
                if grid[irow][icol] != '0' and grid[irow][icol] != '-1':
                    ans = max(dfs(grid, irow, icol, grid[irow][icol]), ans)
        return ans