Techgig

Game Center | Prime Code Champ - techgig

You and your friend go to a game arcade where you choose to play the game Lucky Pick. In the game, there is a square grid and on each block, some money is placed on it. When a player chooses a block, the machine randomly chooses a block from the neighboring ones and the chosen block (consider 8 neighborhood). The player is awarded the money that is placed on the block that the machine selects. Your friend needs help choosing the block.

Your job is to return the block position(s) that will maximize the minimum amount your friend will win for sure. If there are more than one such block positions then the output must return for all these positions.

Input Format
You will be given the Grid Description as -
The first line consists of the size of the square grid (N)
The next N lines each containing N numbers separated by '#', each number representing the amount of money put on that block


Constraints
1 < N < 500

Output Format
You need to print the array of string containing the position(s) of a block choosing which will give the maximum amount of money which your friend will definitely win.

Sample TestCase 1
Input
3
12#45#33
94#54#23
98#59#27
Output
3#1
Explanation

In the above example, if he selects the block (3,1), then under the best case, he could win is 98 and under the worst case the maximum he could win is 54. In such scenario, the worst case of block (3,1) gives your friend more money than the worst case of other blocks.

Sample TestCase 2
Input
4
12#45#33#27
94#54#23#53
98#59#27#62
11#51#67#13
Output
1#3
1#4
2#3
2#4
Explanation


Note: If the output array contains multiple strings(block's positions), all the positions must be in the row-wise traversal order. In Example 2, the output is {1#3,1#4,2#3,2#4}. If your function is returning an array that has same elements (block's position) but in the different order, then the output array will be incorrect.

Java Solution
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;

public class CandidateCode {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
int[][] grid = new int[n][n];
for (int i = 0; i < n; i++) {
String[] line = scanner.nextLine().split("#");
for (int j = 0; j < n; j++) {
grid[i][j] = Integer.parseInt(line[j]);
}
}
List<String> result = new ArrayList<>();
int maxMin = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int min = Integer.MAX_VALUE;
for (int x = Math.max(i-1, 0); x <= Math.min(i + 1, n-1); x++) {
for (int y = Math.max(j-1, 0); y <= Math.min(j + 1, n-1); y++) {
min = Math.min(min, grid[x][y]);
}
}
if (min > maxMin) {
maxMin = min;
result.clear();
result.add((i+1) + "#" + (j+1));
} else if (min == maxMin) {
result.add((i+1) + "#" + (j+1));
}
}
}
for (String position : result) {
System.out.println(position);
}
}
}
Python Solution
n = int(input())
grid = []
for i in range(n):
line = list(map(int,input().split('#')))
grid.append(line)

result = []
max_min = -1000000
for i in range(n):
for j in range(n):
mini = 1000000
for x in range(max(i-1, 0), min(i + 2, n)):
for y in range(max(j-1, 0), min(j + 2, n)):
mini = min(mini, grid[x][y])
if mini > max_min:
max_min = mini
result.clear()
result.append(str(i+1) + "#" + str(j+1))
elif mini == max_min:
result.append(str(i+1) + "#" + str(j+1))

for position in result:
print(position)