Any square grid can be viewed as one or more rings, one inside the other. For example, as shown in figure (a), a 5 * 5 grid is made of three rings, numbered 1,2 and 3 (from outside to inside.) A square grid of size N is said to be sorted, if it includes the values from 1 to N2 in a row-major order, as shown in figure (b) for N = 4. We would like to determine if a given square grid can be sorted by only rotating its rings. For example, the grid in figure (c) can be sorted by rotating the first ring two places counter-clockwise, and rotating the second ring one place in the clockwise direction.
Input
Your program will be tested on one or more test cases. The first input line of a test case is an integer N which is the size of the grid. N input lines will follow, each line made of N integer values specifying the values in the grid in a row-major order. Note than 0 < N ≤ 1, 000 and grid values are natural numbers less than or equal to 1,000,000.
The end of the test cases is identified with a dummy test case with N = 0.
Output
For each test case, output the result on a single line using the following format:
k._result
Where k is the test case number (starting at 1,) _ is a single space, and result is "YES" or "NO" (without the double quotes.)
Sample Input
4
9 5 1 2
13 7 11 3
14 6 10 4
15 16 12 8
3
1 2 3
5 6 7
8 9 4
0
Sample Output
1. YES
2. NO
SOLUCION
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
/**
*
* @author Luis Carlos
*/
public class rings {
private BufferedReader bf = null;
public rings() {
}
public static void main(String arg[]) {
rings e = new rings();
try {
File f = new File("C:/Users/Luis Carlos/Documents/NetBeansProjects/Maraton/src/rings.in");
e.bf = new BufferedReader(new FileReader(f));
String orden = e.bf.readLine();
int numeroLinea = 1;
while (orden != null && !orden.equals("0")) {
int[][] matriz = new int[Integer.parseInt(orden)][Integer.parseInt(orden)];
for (int i = 0; i < Integer.parseInt(orden); i++) {
String[] sp = e.bf.readLine().split(" ");
for (int j = 0; j < Integer.parseInt(orden); j++) {
matriz[i][j] = Integer.parseInt(sp[j]);
}
}
if (e.isRotatingRing(e.generarAnillos(matriz, matriz.length), e.generarAnillos(null, matriz.length))) {
System.out.println(numeroLinea++ + ". YES");
} else {
System.out.println(numeroLinea++ + ". NO");
}
orden = e.bf.readLine();
}
} catch (IOException e1) {
e1.printStackTrace();
}
}
public ArrayList<Integer>[] generarAnillos(int[][] matriz, int orden) {
ArrayList<Integer>[] anillos = null;
try {
int n = orden, numeroAnillos = (n + 1) / 2;
anillos = new ArrayList[numeroAnillos];
for (int i = 0; i < numeroAnillos; i++) {
anillos[i] = new ArrayList<Integer>();
}
for (int k = 0; k < numeroAnillos; ++k) {
for (int j = k; j < n - k; ++j) {
if (matriz == null) {
anillos[k].add(getElementoPosicion(k, j, n));
} else {
anillos[k].add(matriz[k][j]);
System.out.println("Anillo " + k + " " + matriz[k][j]);
}
}
for (int i = k + 1; i <= n - k - 2; ++i) {
if (matriz == null) {
anillos[k].add(getElementoPosicion(i, n - k - 1, n));
} else {
anillos[k].add(matriz[i][n - k - 1]);
System.out.println("Anillo " + k + " " + matriz[i][n - k - 1]);
}
}
for (int j = n - k - 1; j >= k; --j) {
if (matriz == null) {
anillos[k].add(getElementoPosicion(n - k - 1, j, n));
} else {
anillos[k].add(matriz[n - k - 1][j]);
System.out.println("Anillo " + k + " " + matriz[n - k - 1][j]);
}
}
for (int i = n - k - 2; i > k; --i) {
if (matriz == null) {
anillos[k].add(getElementoPosicion(i, k, n));
} else {
anillos[k].add(matriz[i][k]);
System.out.println("Anillo " + k + " " + matriz[i][k]);
}
}
}
if (n % 2 != 0) {
anillos[numeroAnillos - 1].remove(anillos[numeroAnillos - 1].size() - 1);
}
} catch (Exception e) {
e.printStackTrace();
} finally {
return anillos;
}
}
public int getElementoPosicion(int i, int j, int n) {
return i * n + j + 1;
}
public boolean isRotatingRing(ArrayList<Integer>[] real, ArrayList<Integer>[] referencia) {
boolean rotatingRing = true;
for (int i = 0; i < referencia.length; i++) {
ArrayList<Integer> arrayList = referencia[i];
ArrayList<Integer> auxiliarComparacion = new ArrayList<Integer>();
if (real[i].contains(arrayList.get(0))) {
auxiliarComparacion.addAll(real[i].subList(real[i].indexOf(arrayList.get(0)), real[i].size()));
auxiliarComparacion.addAll(real[i].subList(0, real[i].indexOf(arrayList.get(0))));
if (!arrayList.equals(auxiliarComparacion)) {
rotatingRing = false;
break;
}
} else {
rotatingRing = false;
break;
}
}
return rotatingRing;
}
}
