Skip to content

Instantly share code, notes, and snippets.

@ybonnel
Created May 13, 2014 08:31
Show Gist options
  • Save ybonnel/3c58ca020ebe4628fd58 to your computer and use it in GitHub Desktop.
Save ybonnel/3c58ca020ebe4628fd58 to your computer and use it in GitHub Desktop.
Solution for Surface on codingame
// Read inputs from System.in, Write outputs to System.out.
// Your class name has to be Solution
import java.util.*;
import java.io.*;
import java.math.*;
class Solution {
static boolean[][] terrain;
static int largeur;
static int hauteur;
private static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
Point point = (Point) o;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
public List<Point> next() {
List<Point> result = new ArrayList<Point>();
if (x > 0) {
result.add(new Point(x - 1, y));
}
if (x < largeur-1) {
result.add(new Point(x + 1, y));
}
if (y > 0) {
result.add(new Point(x, y - 1));
}
if (y < hauteur-1) {
result.add(new Point(x, y + 1));
}
return result;
}
}
private static void init(Scanner in) {
largeur = in.nextInt();
hauteur = in.nextInt();in.nextLine();
terrain = new boolean[largeur][hauteur];
for (int y = 0; y < hauteur; y++) {
String line = in.nextLine();
for (int x = 0; x < largeur; x++) {
terrain[x][y] = false;
if (line.charAt(x) == 'O') {
terrain[x][y] = true;
}
}
}
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
init(in);
int nbTests = in.nextInt();
for (int i = 0; i< nbTests; i++) {
int x = in.nextInt();
int y = in.nextInt();
System.out.println(tailleLac(new Point(x, y)));
}
}
public static int tailleLac(Point point) {
LinkedList<Point> pointToExplore = new LinkedList<Point>();
Set<Point> pointExplored = new HashSet<Point>();
pointToExplore.add(point);
int tailleLac = 0;
while (!pointToExplore.isEmpty()) {
Point next = pointToExplore.removeFirst();
if (!pointExplored.contains(next)
&& terrain[next.x][next.y]) {
tailleLac++;
pointExplored.add(next);
pointToExplore.addAll(next.next());
}
}
return tailleLac;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment