讨论/题目交流/1277.统计全为1的正方形子矩阵,我这个错哪里了啊/
1277.统计全为1的正方形子矩阵,我这个错哪里了啊

我想的是dp+bfs,首先对于dp[i][j]记录的是到(i,j)一共有多少个正方形。
然后转移方程就是dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+bfs(i,j,matrix),bfs用来计算以(i,j)为右下角节点的正方形。
然后卡在了第22个特别大的用例,同时我自己造了一个小的,也多了1:[[0,1,1,0],[1,1,1,1],[0,1,1,1],[1,1,1,1],[1,0,1,1]]
跪谢大佬们了
弄不出来睡不着觉啊,不知道错哪里了难受

class Solution {
    public int countSquares(int[][] matrix) {
        if(matrix.length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        if(matrix[0][0] == 0)
            dp[0][0] = 0;
        else dp[0][0] = 1;
        for(int i = 1; i < n; i++) {
            if(matrix[0][i] == 1)
                dp[0][i] = dp[0][i - 1] + 1;
            else
                dp[0][i] = dp[0][i - 1];
        }
        for(int i = 1; i < m; i++) {
            if(matrix[i][0] == 1)
                dp[i][0] = dp[i - 1][0] + 1;
            else
                dp[i][0] = dp[i - 1][0];
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
                if(matrix[i][j] == 1)
                    dp[i][j] += bfs(i, j, matrix);
            }
        }
        return dp[m-1][n-1];
    }
    private int bfs(int i, int j, int[][] matrix) {
        Queue<int[]> queue = new LinkedList<>();
        int index = 0;
        int n = Math.min(i, j);
        queue.offer(new int[]{i, j});
        while(index <= n) {
            Queue<int[]> temp = new LinkedList<>();
            boolean flag = true;
            while(!queue.isEmpty()) {
                int[] node = queue.poll();
                int x = node[0];
                int y = node[1];
                if(matrix[x][y] != 1) {
                    flag = false;
                    break;
                }
                //当x,y与i,j在同一个斜对角线上时
                if(i - x == j - y) {
                    temp.offer(new int[]{x - 1, y - 1});
                    temp.offer(new int[]{x - 1, y});
                    temp.offer(new int[]{x, y - 1});
                } else if(i - x > y - j) {//在对角线的右上半边
                    temp.offer(new int[]{x - 1, y});
                } else if(i - x < y - j) {//在对角线的左下半边
                    temp.offer(new int[]{x, y - 1});
                }
                    
            }
            //如果有一个不为1,就终止,直接返回当前遍历的正方形个数
            if(flag == false)
                break;
            else index++;
            queue = temp;
        }
        return index;
    }
}
展开讨论
共 1 个讨论

想明白了,bfs添加非对角线元素添加错了,y和j写反了