CodinGame JULY 2013 #2

CodinGame-JULY2013-2-Solution.java

/**
« Les guerres du XXIe siècle auront l'eau pour enjeu ».
Limitée, l'eau douce disponible n'est pourtant pas rare. Sa quantité pourrait largement combler les besoins actuels de la population mondiale mais faudrait-il encore être capable de localiser et de mesurer les étendues d’eau disponibles sur une zone géographique !

Votre mission
Déterminer avec précision des superficies d’étendues d'eau. Vous disposez d'une carte décrivant le contenu de chaque mètre carré d’une zone géographique. Un mètre carré est constitué soit de terre, soit d'eau.

Voici un exemple de carte :
Les cases vertes représentent la terre et les cases bleues représentent l'eau. Un lac est constitué d'un ensemble de cases d'eau adjacentes horizontalement ou verticalement. Deux cases uniquement adjacentes en diagonale ne font pas partie d’un même lac.

Votre programme reçoit en entrée une liste de coordonnées, pour chacune vous devez déterminer la superficie du lac qui s'y trouve. S’il n'y a pas de lac, alors la superficie est égale à 0. Dans cet exemple, le lac qui se trouve en coordonnée (1, 2) a une superficie de 3 mètres carrés.

Format de la carte
Une carte est également fournie en entrée sous le format ASCII, le caractère # représente la terre, la lettre O majuscule représente l'eau. Dans ce format, la carte ci-dessus est représentée ainsi :

####
##O#
#OO#
####

Une carte peut contenir plusieurs étendues d'eau distinctes.
​
ENTRÉE :
Ligne 1 : la largeur L de la carte
Ligne 2 : la hauteur H de la carte
H lignes suivantes : L caractères # ou O
Ligne suivante : le nombre N de coordonnées à tester
N lignes suivantes : les coordonnées X Y à tester, séparées par un espace
 
SORTIE :
N lignes, chacune affichant la superficie du lac situé aux coordonnées fournies en entrée.
 
CONTRAINTES :
0 < L < 10000
0 < H < 10000
0 <= X < L
0 <= Y < H
0 < N < 1000
 
EXEMPLE :
Entrée
4
4
####
##O#
#OO#
####
3
0 0
1 2
2 1
Sortie
0
3
3
 

*/
/**
 * CodinGame
 * */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Solution
 * */
public class Solution {
    private static Solution solution=new Solution();

  /**
   * Cell
	 * */
	private class Cell{
		Integer rowId;
		Integer columnId;
		Boolean isWater=false;
		Integer lacId=0;
		
		/**/
		public Cell(Integer rowId,Integer columnId){
			this.rowId=rowId;
			this.columnId=columnId;
		}
	}
	private Cell newCell(Integer rowId,Integer columnId){ return new Cell(rowId,columnId); }
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		// Standard Input
    	BufferedReader reader =new BufferedReader(new InputStreamReader(System.in)); 
    	
    	try {

    		/**/
    		Integer c=Integer.valueOf(reader.readLine().trim()); // Columns
			Integer r=Integer.valueOf(reader.readLine().trim()); // Rows			
			Cell[][] cells=new Cell[r][c];

			/**/
			for(int i=0;i!=r;i++){
				char[] chars=reader.readLine().trim().toCharArray();
				for(int j=0;j!=chars.length;j++){
					cells[i][j]=solution.newCell(i, j);
					cells[i][j].isWater=(chars[j]=='O');
				}
			}
			
			/**/
			int cLacs=0;
			for(int i=0;i!=r;i++){
				for(int j=0;j!=c;j++){
					Cell cell=cells[i][j];
					if(cell.isWater&&(cell.lacId==0)){
						
						cell.lacId=(++cLacs); // New Lac. 
						
						List<Cell> listCells=Collections.synchronizedList(new ArrayList<Cell>());
						listCells.add(cell);
						while(!listCells.isEmpty()){
							Cell iterCell=listCells.remove(0);
							// Up
							if(iterCell.rowId>0){
								Cell nextCell=cells[iterCell.rowId-1][iterCell.columnId];
								if(nextCell.isWater&&(nextCell.lacId==0)){
									nextCell.lacId=iterCell.lacId;
									listCells.add(nextCell);
								}									
							}
							// Down
							if((iterCell.rowId+1)<r){
								Cell nextCell=cells[iterCell.rowId+1][iterCell.columnId];								
								if(nextCell.isWater&&(nextCell.lacId==0)){
									nextCell.lacId=iterCell.lacId;
									listCells.add(nextCell);
								}									
							}
							// Left
							if(iterCell.columnId>0){
								Cell nextCell=cells[iterCell.rowId][iterCell.columnId-1];								
								if(nextCell.isWater&&(nextCell.lacId==0)){
									nextCell.lacId=iterCell.lacId;
									listCells.add(nextCell);
								}									
							}
							// Right
							if((iterCell.columnId+1)<c){
								Cell nextCell=cells[iterCell.rowId][iterCell.columnId+1];
								if(nextCell.isWater&&(nextCell.lacId==0)){
									nextCell.lacId=iterCell.lacId;
									listCells.add(nextCell);
								}									
							}
						}
						
					}
				}
			}
			
			/* Lacs*/
			int[] rLacs=new int[cLacs+1];
			if(cLacs>0){				
				for(int i=0;i!=r;i++)
					for(int j=0;j!=c;j++)
						rLacs[cells[i][j].lacId]++;				
			}
			
			/* Queries */
			Integer nQueries=Integer.valueOf(reader.readLine().trim());
			for(int i=0;i!=nQueries;i++){
				String[] q=reader.readLine().trim().split(" ", 2);
				Integer columnId=Integer.valueOf(q[0].trim());
				Integer rowId=Integer.valueOf(q[1].trim());
				Cell cell=cells[rowId][columnId];
				System.out.println(cell.isWater?rLacs[cell.lacId]:0);
			}
			
			reader.close();
						
		} catch (IOException e) {
			
			e.printStackTrace();
		} 
	}
}