/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    bool isDifferent(vector<vector<int>>& grid, int rowStart, int rowEnd, int colStart, int colEnd) {
        int curr = grid[rowStart][colStart];

        for(int i = rowStart; i <= rowEnd; i++) {
            for(int j = colStart; j <= colEnd; j++) {
                if(grid[i][j] != curr) return true;
            }
        }
        return false;
    }

    Node* build(vector<vector<int>>& grid, int rowStart, int rowEnd, int colStart, int colEnd) {
        Node* root = new Node();
        root->val = 1;
        
        if(isDifferent(grid, rowStart, rowEnd, colStart, colEnd) == false) {
            root->val = grid[rowStart][colStart];
            root->isLeaf = true;
            return root;
        }
        
        int rowMid = rowStart + (rowEnd - rowStart) / 2;
        int colMid = colStart + (colEnd - colStart) / 2;
        root->topLeft = build(grid, rowStart, rowMid, colStart, colMid);
        root->topRight = build(grid, rowStart, rowMid, colMid+1, colEnd);
        root->bottomLeft = build(grid, rowMid+1, rowEnd, colStart, colMid);
        root->bottomRight = build(grid, rowMid+1, rowEnd, colMid+1, colEnd);
        return root;
    }

    Node* construct(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        return build(grid, 0, m-1, 0, n-1);
    }
};