Uniform Distribution in Square
An uniform distribution of an n xn square array of cells is a partition of the n*n cells in the array inexactly n sets, each one with n contiguous cells. Two cells are contiguous when they have a common side.
A good uniform distribution is composed of contiguous regions. The figures show a good and a wrong uniform distribution for a 5 x 5 square:
Note that in the second example the cells labeled with 4 describe three non-contiguous regions and cells labeled with 5describe two non-contiguous regions. You must write a program that evaluates if an uniform distribution of the cells in a square array is good or not.
Input
The first line contains the number of test cases. Test cases follow in next lines.
It is understood that a cell in an n x n square array is denoted by a pair (i, j),with 1 <= i , j<= n. The input file contains several test cases. Each test case begins with a line indicating n, 0<="" style="margin: 0px; padding: 0px;">100,the side of the square array to be partitioned. Next, there are n-1 lines, each one corresponding to one partition of the cells of the square, with some non-negative integer numbers. Consecutive integers in a line are separated with a single blank character. A line of the form
a1 a2 a3 a4…
means that cells denoted with the pairs (a1,a2),(a3, a4), ... belong to one of the areas in the partition.
The last area in the partition is defined by those cells not mentioned in the n- 1 given lines.
Output
For each test case ‘good’ must be printed if the uniform distribution is good, in other case, ‘wrong’ must be
printed. The answers for the different cases must preserve the order of the input. The first output line for each test case should be "Case #tn", where tn is the test case number.
Sample
Input
3
2
1 2 2 1
5
1 1 1 2 1 3 3 2 2 2
2 1 4 2 4 1 5 1 3 1
4 5 5 2 5 3 5 5 5 4
2 5 3 4 3 5 4 3 4 4
5
1 1 1 2 1 3 3 2 2 2
2 1 3 1 4 1 5 1 4 2
4 5 5 2 5 3 5 5 5 4
2 4 1 4 3 5 4 3 4 4
Output
Case #1
wrong
Case #2
good
Case #3
wrong
Code:
package UniformDistribution;
import java.io.FileInputStream;
import java.util.Scanner;
public class uniformDistribution {
static int [][] map;
static int [][] arr1;
static int N;
static int [] dx = {-1, 0, 1, 0};
static int [] dy = {0, 1, 0, -1};
static void move(int x, int y, int k) {
map[x][y] = 0;
for (int i = 0; i < 4; i++) {
int x1 = x+dx[i];
int y1 = y+dy[i];
if (x1 >= 0 && x1 < N && y1 < N && y1 >= 0 && map[x1][y1] == k) {
move(x1, y1, k);
}
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("D://Trainee//SRV_training//src//UniformDistribution//uniform.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++) {
N = sc.nextInt();
map = new int [N][N];
arr1 = new int [2][N];
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
int x = sc.nextInt()-1;
int y = sc.nextInt()-1;
map[x][y] = i;
if (j == 0) {
arr1[0][i-1] = x;
arr1[1][i-1] = y;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) {
map[i][j] = N;
arr1[0][N-1] = i;
arr1[1][N-1] = j;
}
}
}
for (int i = 0; i < N; i++) {
move(arr1[0][i], arr1[1][i], (i+1));
}
String Ans = "Valid";
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] != 0) {
Ans = "Invalid";
break;
}
}
}
System.out.println("#" + test_case + " " + Ans);
}
}
}