Minimum number of integers required to fill the NxM grid

Given a grid of size (NxM) is to be filled with integers. Filling of cells in the grid should be done in the following manner:

1. let A, B and C are three cell and, B and C shared a side with A.
2. Value of cell B and C must be distinct.
3. Let L be the number of distinct integers in a grid.
4. Each cell should contain value from 1 to L.

The task is to find the minimum value of L and any resulting grid. Examples:

Input: N = 1, M = 2
Output:
L = 2
grid = {1, 2}

Input: 2 3
Output:
L = 3
grid = {{1, 2, 3},
        {1, 2, 3}}
Explanation: Integers in the neighbors 
of cell (2, 2) are 1, 2 and 3.
All numbers are pairwise distinct.

Approach: It is given that two cells shared a side with another cell must be distinct. For each such cell, there will be a possible maximum of 8 cells in a grid from whom its value must be different. It will follow the 4 colour problem: Maximum colour required to fill the regions will be 4.

1. For N<4 or M<4 Number of integers required may vary from 1 to 4. Checking 8 cells and then fill the current cell. If number of distinct integers in 8 cells is less than L then fill the current cell with any remaining integer, otherwise fill the current cells with L+1 integer.
2. For N>=4 and M>=4 Number of integers required must be 4 according to 4 colour problem. Use the 4×4 matrix to fill the NxM matrix.

1 2 3 4
1 2 3 4
3 4 1 2
3 4 1 2

Below is the implementation of the above approach: Implementation: 

4
1 2 3 4 1 
1 2 3 4 1 
3 4 1 2 3 
3 4 1 2 3 
1 2 3 4 1 
1 2 3 4 1 
3 4 1 2 3 
3 4 1 2 3 
1 2 3 4 1 
1 2 3 4 1 

Time Complexity: O(N*M)
Auxiliary Space: O(N*M)