Lucky Group

Ninja
0/200
Average time to solve is 80m
5 upvotes
Asked in company
Codenation

Problem statement

Ninja considers himself a master in solving sudoku. To test his problem-solving skills, one day his friend asked him to solve a problem based on the grid. The problem is as follow :

There is a grid of ‘N’ rows and ‘M’ columns consisting of four digits 0, 1, 2, and 3.

We call a four-cell group a “lucky group” if and only if :

1. The number on these cells form a permutation of the set {0,1, 2, 3}.
2. The cell marked 1 is directly reachable from the cell marked 0.
3. The cell marked 2 is directly reachable from cell marked 1.
4. The cell marked 3 is directly reachable from cell marked 2.

A cell is said to be directly reachable from another cell if they share one side.

Given the constraint that each cell can be part of at most 1 "lucky Group". Your task is to find the maximum number of “Lucky Group”.

Since Ninja finds this problem very different and difficult from the sudoku problem. He needs your help. Can you solve the problem on his behalf?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test cases follow.

The first line of each test case contains two integers ‘N’ and  ‘M’, denoting the number of rows and columns in a given grid.

The next ‘N’ line contains ‘M’ space-separated integers consisting of either 0, 1, 2 or 3 denoting the grid cell.
Output Format: 
The first line of each test case contains one integer ‘X’, denoting the maximum number of “Lucky Group”.

The output of each test case will be printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N, M <= 20
0 <= cell[i][j] <= 3

Time Limit: 1 sec.
Sample Input 1:
2
2 2
0 1
3 2
2 4
0 1 2 2
0 2 3 3
Sample Output 1:
1
1
Explanation of Sample Output1:
In the first test case, cells (0,0) --> (0,1)  -->(1, 1) --> (1, 0) form one lucky group.

In the second test case, cells (0,0) --> (0,1)  -->(0, 2) --> (1, 2) form one lucky group. We can prove that there is no more than one lucky group.
Sample Input 2:
2
3 4
0 1 0 1
3 2 3 2
3 0 1 3
5 2
0 1
1 1
2 3
1 1
0 0
Sample Output 2:
2
1
Hint

Can you convert this question to the max-flow problem? Split the nodes with values 1 and 2 into two nodes.

Approaches (1)
Max-Flow in graph

This problem can be solved using maximum flow concept.

 

Consider the following network:

  • For each cell of the grid marked '0' and '3' we have one node in the network.
  • For each cell of the grid marked '1' and '2' we have 2 nodes in the network, we will call the first node as the true node and the second node as the dummy node.
  • We also have 2 extra nodes representing source and sink.


 We add the following edges to our network.

  • For each cell marked '0' we add an edge of capacity 1 from the source to the node corresponding to this cell.
  • For each cell marked '3' we add an edge of capacity 1 from the node corresponding to this cell to the sink.
  • For each cell marked '0' we add an edge of capacity 1 from the node corresponding to this cell to the true node corresponding to a cell marked with '1' and is directly reachable from this cell.
  • For each cell marked with '1' we add an edge of capacity 1 from the true node corresponding to this cell to the dummy node corresponding to this cell.
  • For each cell marked '1' we add an edge of capacity 1 from the dummy node corresponding to this cell to the true node corresponding to a cell marked with '2' and is directly reachable from this cell.
  • For each cell marked with '2' we add an edge of capacity 1 from the true node corresponding to this cell to the dummy node corresponding to this cell.
  • For each cell marked '2' we add an edge of capacity 1 from the dummy node corresponding to this cell to the node corresponding to a cell marked with '3' and is directly reachable from this cell.
     The answer is the maximum flow in the above-constructed network.

 

Algorithm:

 

Let ‘countGroup(grid, n, m)’ be the function that returns the maximum number of lucky groups.

 

The steps are as follows :

  • Take an array of a list to store the graph.
  • Take a 2D array ‘capacity’ to store the capacity of each edge.
  • Take an array ‘X’, initialize it with {1, -1, 0, 0}.
  • Take an array ‘Y’, initialize it with {0, 0, 1, -1}.
  • Run a loop from 0 to n:
    • Run a loop from 0 to m:
      • Take variable ‘node’ and initialize it with (i * m) + j +1
      • Check if grid[i][j] is equal to 0
        • Run a loop from 0 to 4
          • Take a variable  ‘nx’ and calculate the row of the next adjacent cell as i + X[k]
          • Take a variable  ‘ny’ and calculate the column of the next adjacent cell as i + Y[k].
          • If adjacent cell (‘nx’, ‘ny’) is valid and grid[nx][ny] is equal to 1
            • Calculate true node ‘trueOne’ = nx * m + ny +1.
            • Calculate dummy node ‘dummyOne’ = (nx + n) * m + ny +1
            • Create an edge between ‘node’ and ‘trueOne’.
            • Create an edge between ‘dummyOne’ and ‘trueOne’.
            • Create an edge between ‘0’ and ‘node’
            • Store capacity[node][trueOne] = 1.
            • Store capacity[trueOne][dummyOne] = 1.
            • Store capacity[0][node] = 1.
      • Check if grid[i][j] is equal to 1
        • Run a loop from 0 to 4
          • Take a variable  ‘nx’ and calculate the row of the next adjacent cell as i + X[k]
          • Take a variable  ‘ny’ and calculate the column of the next adjacent cell as i + Y[k].
          • If adjacent cell (‘nx’, ‘ny’) is valid and grid[nx][ny] is equal to 2
            • Calculate true node ‘trueOne’ = nx * m + ny +1.
            • Calculate dummy node ‘dummyOne’ = (nx + n) * m + ny +1
            • Create an edge between ‘node’ and ‘trueOne’
            • Create an edge between ‘dummyOne’ and ‘trueOne’
            • Store capacity[node][trueOne] = 1.
            • Store capacity[trueOne][dummyOne] = 1.
      • Check if grid[i][j] is equal to 2
        • Run a loop from 0 to 4
          • Take a variable  ‘nx’ and calculate the row of the next adjacent cell as i + X[k]
          • Take a variable  ‘ny’ and calculate the column of the next adjacent cell as i + Y[k].
          • If adjacent cell (‘nx’, ‘ny’) is valid and grid[nx][ny] is equal to 3
            • Calculate true node ‘trueOne’ = nx * m + ny +1.
            • Create an edge between ‘node’ and ‘trueOne’.
            • Store capacity[node][trueOne] = 1.
          • Else
            • Create an edge between ‘node’ and sink(2 * n * m + 1)
            • ’Store capacity[node][2 * n * m + 1] = 1.
  • Now use the standard maximum-flow algorithm considering 0 as the source and 2 * n *m +1 as sink and store the answer in ‘ans’
  • Return ‘ans’ as the final answer.
Time Complexity

O(N * M) ^ 2. , where ‘N’ is the number of rows and ‘M’ is the number of columns in a given grid.


 The time taken to create graph O( N * M) . The time taken to find max- flow is O( edges * maxFlow ) = O( (N * M * 2) * ( N * M / 2) ) =O (N * M) ^ 2. 

Space Complexity

 O(M * N), where ‘N’ is the number of rows and ‘M’ is the number of columns in a given grid.

 

Mainly, We are using space in creating a graph, which takes O(N * M) space. Hence, the space complexity is  O(N * M).

Code Solution
(100% EXP penalty)
Lucky Group
Full screen
Console