[Solved] Asya has been traveling different worlds after building a portal for herself

Asya has been traveling different worlds after building a portal for herself. This time she has reached the strange world. This world can be represented as a finite cartesian-coordinate-system

This world is inhabited by Locks and Keys, every lock and key is placed on some integral point on the cartesian plane. These locks and keys can also move but only either parallel to the X-axis or to the Y-axis and they can’t change their direction once they start moving from their original positions.

Once a lock and key meet, they can either continue their movement or they can come out of the cartesian plane and Asya can take that pair back home. Asya knows the original position of all the locks and keys and she wants to take as many pairs as possible, with her. For this, she needs to decide the direction of movement for all the locks and keys and when they make a pair

Once Asya has decided the direction of movement for every

element, the elements start moving in the assigned direction with a speed of 1-unit per unit of time:

Help her find out the maximum number of pairs she can take with her if she assigns the directions optimally.

Input Format: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N and M, N is the number of rows and M is the number of columns in the grid. The second line of each test case contains N*M space-separated integers.

Output Format: Print the maximum number of pairs that can be taken.

Input:

1
3 3
0 1 0
0 0 2
0 0 0

Output:

2

Solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] arr = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }
            int[][] dp = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] == 1) {
                        dp[i][j] = 1;
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] == 1) {
                        int x = i;
                        int y = j;
                        while (x < n && y < m) {
                            if (arr[x][y] == 2) {
                                dp[x][y] = Math.max(dp[x][y], dp[i][j] + 1);
                                // sauravhathi
                            }
                            x++;
                            y++;
                        }
                    }
                }
            }
            int max = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    max = Math.max(max, dp[i][j]);
                }
            }
            System.out.println(max);
        }
    }
}

Happy Learning – If you require any further information, feel free to contact me.