/* Verifica se una scacchiera contiene almeno due regine
 * che si possono mangiare a vicenda.
 * La posizione delle regine su una scacchiera e' rappresentata
 * dalla presenza del valore 1
 */
public class ControllaRegine {

	public static void stampaScacchiera(int[][] a) {
		for(int i=0; i<a.length; i++) {
			for(int j=0; j<a[i].length; j++)
				System.out.print(a[i][j]);
			System.out.println();
		}
	}

	/* assumiamo che la matrice sc sia quadrata
	 * Questo metodo si puo' migliorare leggermente
	 */
	public static boolean siMangiano(int[][] sc) {
		int n = sc.length; // n e' sia il numero di righe che il numero di colonne
		for(int i=0; i<n; i++) {
			if(numRegineInRiga(sc, i) > 1)
				return true;
			if(numRegineInColonna(sc, i) > 1)
				return true;
		}

		for(int i=0; i<n-1; i++)
			// controlla la diagonale incrementando i e j
			// partendo da prima colonna
			if(numRegineInDiagIncrIeIncrJ(sc, i, 0) > 1)
				return true;
		for(int i=1; i<n-1; i++)
			// controlla la diagonale incrementando i e j
			// partendo da prima riga
			if(numRegineInDiagIncrIeIncrJ(sc, 0, i) > 1)
				return true;
		for(int i=1; i<n; i++)
			// controlla la diagonale incrementando i e decrementando j
			// partendo da prima riga
			if(numRegineInDiagIncrIeDecrJ(sc, 0, i) > 1)
				return true;
		for(int i=1; i<n-1; i++)
			// controlla la diagonale incrementando i e decrementando j
			// partendo da ultima colonna
			if(numRegineInDiagIncrIeDecrJ(sc, i, n-1) > 1)
				return true;
		return false;
	}

// TUTTI I METODI SEGUENTI SI POSSONO MIGLIORARE INTERROMPENDO
// IL CICLO APPENA SI RAGGIUNGE IL VALORE 2	
	public static int numRegineInRiga(int[][] a, int riga) {
		int numInRiga = 0;
		for(int j=0; j<a[riga].length; j++)
			if(a[riga][j] == 1)
				numInRiga++;
		return numInRiga;
	}
	
	public static int numRegineInColonna(int[][] a, int colonna) {
		int numInColonna = 0;
		for(int i=0; i<a.length; i++)
			if(a[i][colonna] == 1)
				numInColonna++;
		return numInColonna;
	}

	// scandisce in obliquo incrementando indice di riga e incrementando indice di colonna
	public static int numRegineInDiagIncrIeIncrJ(int[][] a, int rIniz, int cIniz) {
		int numRegine = 0;
		int i=rIniz;
		int j=cIniz;
		while(i<a.length && j<a[0].length) {
			if(a[i][j] == 1)
				numRegine++;
			i++;
			j++;
		}
		return numRegine;
	}
	
	// scandisce in obliquo incrementando indice di riga e decrementando indice di colonna
	public static int numRegineInDiagIncrIeDecrJ(int[][] a, int rIniz, int cIniz) {
		int numRegine = 0;
		int i=rIniz;
		int j=cIniz;
		while(i<a.length && j>=0) {
			if(a[i][j] == 1)
				numRegine++;
			i++;
			j--;
		}
		return numRegine;
	}
	
	public static void main(String[] args) {
		int[][] scac1 = {
			{1, 0, 0, 0, 0, 0, 0, 0},
			{1, 0, 0, 0, 0, 0, 0, 0},
			{1, 0, 0, 0, 0, 0, 0, 0},
			{1, 0, 0, 0, 0, 0, 0, 0},
			{1, 0, 0, 0, 0, 0, 0, 0},
			{1, 0, 0, 0, 0, 0, 0, 0},
			{1, 0, 0, 0, 0, 0, 0, 0},
			{1, 0, 0, 0, 0, 0, 0, 0},
		};
		int[][] scac2 = {
			{0, 1, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 1, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 1},
			{1, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 1, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 1},
			{0, 0, 0, 1, 0, 0, 0, 0},
		};

		stampaScacchiera(scac1);
		if(siMangiano(scac1))
			System.out.println("si mangiano");
		else
			System.out.println("non si mangiano");

		System.out.println();
		stampaScacchiera(scac2);
		if(siMangiano(scac2))
			System.out.println("si mangiano");
		else
			System.out.println("non si mangiano");
	}
}