import java.util.Arrays;

public class RobotPlacement {
	public static void main(String[] args) {
		char[][] areaA = {   {'-','-','-','-','R'}, 
						     {'-','R','-','-','-'},
							 {'-','-','-','R','-'},
							 {'-','-','R','-','-'},
							 {'-','-','R','-','-'}  };
		int[] conflictingRobotsA = findConflictingRobot(areaA);
		System.out.println(Arrays.toString(conflictingRobotsA));
		
		char[][] areaB = {   {'-','-','-','-','-'}, 
							 {'-','-','-','-','-'},
							 {'-','T','T','-','-'},
							 {'-','T','T','-','-'},
							 {'-','-','-','-','-'}  };
		char[][] robotsB = placeOtherRobots(areaB);
		System.out.println(Arrays.deepToString(robotsB));
		
		char[][] areaC = {   {'-','-','-','-','-'}, 
							 {'-','-','-','-','-'},
							 {'R','T','T','-','-'},
							 {'-','T','T','R','-'},
							 {'-','-','-','-','-'}  };
		char[][] robotsC = placeOtherRobots(areaC);
		System.out.println(Arrays.deepToString(robotsC));
	}

	// Find a robot that blocks other robots' lazer light
	public static int[] findConflictingRobot(char[][] area) {
		int h = area.length;
		//itterate over the area
		for(int i = 0; i < h; i++) {
			for(int k = 0; k < h; k++) {
				//if we have a Robot
				if(area[i][k]=='R') {
					//check if there is a conflict
					if(!isPlacedOk(area, i, k)) {
						//return index if there is a conflict
						int[] res = {i,k};
						return res;
					}
				}
			}
		}
		//if there was no conflict return null
		return null;
	}
	
	//checks in all directions for conflicts with other Robots.
	public static boolean isPlacedOk(char[][] area, int i, int k) {
		int h = area[0].length;
		//check down
		for(int l = i-1;  l>= 0; l--) {
			if(area[l][k] == 'R') {
				return false;
			}
		}
		//check up
		for(int l = i+1;  l < h; l++) {
			if(area[l][k] == 'R') {
				return false;
			}
		}
		//check left
		for(int m = k-1;  m>= 0; m--) {
			if(area[i][m] == 'R') {
				return false;
			}
		}
		//check Right 
		for(int m = k+1;  m < h; m++) {
			if(area[i][m] == 'R') {
				return false;
			}
		}
		
		//check diagonal left up
		int n = 1;
		while(i - n >= 0 && k-n >= 0) {
			if(area[i-n][k-n] == 'R') {
				return false;
			}
			n++;
		}
		//check diagonal right up
		n = 1;
		while(i - n >= 0 && k+n < h) {
			if(area[i-n][k+n] == 'R') {
				return false;
			}
			n++;
		}
		//check diagonal left down
		n = 1;
		while(i + n < h && k-n >= 0) {
			if(area[i+n][k-n] == 'R') {
				return false;
			}
			n++;
		}
		//check diagonal right down
		n = 1;
		while(i + n < h && k+n < h) {
			if(area[i+n][k+n] == 'R') {
				return false;
			}
			n++;
		}
		//if no check fails return true;
		return true;
	}
	// Place h robots in a h*h area to protect the treasure
	public static char[][] placeRobots(char[][] area) {
		//rec call with additoinal argument 
		return recplaceRobots(area, 0);
	}
	
	//recursive function to place robots
	public static char[][] recplaceRobots(char[][] area, int rowIndex) {
		int h = area.length;
		
		//base case if we have a Robot in each Row
		if(rowIndex == h) {
			//use exercise 1. to check for conflicts
			if(findConflictingRobot(area) == null) {
				return area;
			}
			else {
				return null;
			}
		}
		//only needed for Task 3.
		//checks if there is a given Robot in the current Row
		if(containsRobot(area[rowIndex])) {
			//we skip to the next row
			return recplaceRobots(area, rowIndex +1);
		}
		
		//iterate over the row and try all placements
		for(int k = 0; k < h; k++) {
			//if the index is empty and placement of robot does not conflict with others
			if(area[rowIndex][k] == '-' && isPlacedOk(area, rowIndex, k)) {
				//copy Array
				char[][] newArea = copyArea(area); 
				//place Robot in new Array
				newArea[rowIndex][k] = 'R';
				//call recursion for next rows
				char[][] returned = recplaceRobots(newArea, rowIndex+1);
				//if we found a solution return it else continue loop with next possible placement
				if(returned != null) {
					return returned;
				}
			}
			
		}
		//if we found no solution return null
		return null;
	}
	
	
	//Helper function to Copy an Array
	public static char[][] copyArea(char[][] area){
		int h = area.length;
		char[][] res = new char[h][h];
		for(int i = 0; i < h; i++) {
			for(int k = 0; k < h; k++) {
				res[i][k] = area[i][k];
			}
		}
		return res;
	}
	
	//Helper Function to check if a row has already a Robot
	public static boolean containsRobot(char[] row) {
		int h = row.length;
		for(int i = 0; i < h; i++) {
			if(row[i] == 'R') {
				return true;
			}
		}
		return false;
	}
	// Place other robots with pre-installed robots in a h*h area to protect the treasure
	public static char[][] placeOtherRobots(char[][] area) {
		//same recursive call as for 2.
		return recplaceRobots(area, 0);
	}

}