Problème 1 : Superficie maximale d'une île
Énoncé : Étant donné une grille composée de 1 (terre) et 0 (eau), calculer la superficie maximale des îles. La superficie est le nombre total de cellules terrestres connectées horizontalement ou verticalement.
Exemple d'entrée :
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
Sortei attendue : 4
Approche : Utiliser la recherche en profondeur (DFS) ou en largeur (BFS) pour explorer les composantes connexes.
Implémentation DFS
import java.util.Scanner;
public class MaxArea {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner lecteur = new Scanner(System.in);
int lignes = lecteur.nextInt();
int colonnes = lecteur.nextInt();
int[][] grille = new int[lignes][colonnes];
boolean[][] explore = new boolean[lignes][colonnes];
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
grille[i][j] = lecteur.nextInt();
}
}
int maxSurface = 0;
for (int r = 0; r < lignes; r++) {
for (int c = 0; c < colonnes; c++) {
if (!explore[r][c] && grille[r][c] == 1) {
explore[r][c] = true;
maxSurface = Math.max(maxSurface, parcourirProfondeur(grille, explore, r, c));
}
}
}
System.out.println(maxSurface);
}
private static int parcourirProfondeur(int[][] grille, boolean[][] explore, int x, int y) {
int surface = 1;
for (int[] dir : DIRECTIONS) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < grille.length && ny >= 0 && ny < grille[0].length
&& !explore[nx][ny] && grille[nx][ny] == 1) {
explore[nx][ny] = true;
surface += parcourirProfondeur(grille, explore, nx, ny);
}
}
return surface;
}
}
Implémentation BFS
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class MaxAreaBFS {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner lecteur = new Scanner(System.in);
int lignes = lecteur.nextInt();
int colonnes = lecteur.nextInt();
int[][] grille = new int[lignes][colonnes];
boolean[][] explore = new boolean[lignes][colonnes];
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
grille[i][j] = lecteur.nextInt();
}
}
int maxSurface = 0;
for (int r = 0; r < lignes; r++) {
for (int c = 0; c < colonnes; c++) {
if (!explore[r][c] && grille[r][c] == 1) {
maxSurface = Math.max(maxSurface, parcourirLargeur(grille, explore, r, c));
}
}
}
System.out.println(maxSurface);
}
private static int parcourirLargeur(int[][] grille, boolean[][] explore, int startX, int startY) {
Queue<int> file = new LinkedList<>();
file.offer(new int[]{startX, startY});
explore[startX][startY] = true;
int surface = 0;
while (!file.isEmpty()) {
int[] courant = file.poll();
surface++;
for (int[] dir : DIRECTIONS) {
int nx = courant[0] + dir[0];
int ny = courant[1] + dir[1];
if (nx >= 0 && nx < grille.length && ny >= 0 && ny < grille[0].length
&& !explore[nx][ny] && grille[nx][ny] == 1) {
explore[nx][ny] = true;
file.offer(new int[]{nx, ny});
}
}
}
return surface;
}
}
</int>
Problème 2 : Superficei totale des îles isolées
Énoncé : Calculer la superficie totale des îles qui ne touchent pas les bords de la grille.
Approche : Identifier d'abord les îles non isolées (touchant les bords) et les marquer, puis sommer les superficies des îles restantes.
import java.util.Scanner;
public class TotalIsole {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner lecteur = new Scanner(System.in);
int lignes = lecteur.nextInt();
int colonnes = lecteur.nextInt();
int[][] grille = new int[lignes][colonnes];
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
grille[i][j] = lecteur.nextInt();
}
}
// Marquer les îles touchant les bords
for (int i = 0; i < lignes; i++) {
if (grille[i][0] == 1) marquerNonIsole(grille, i, 0);
if (grille[i][colonnes - 1] == 1) marquerNonIsole(grille, i, colonnes - 1);
}
for (int j = 0; j < colonnes; j++) {
if (grille[0][j] == 1) marquerNonIsole(grille, 0, j);
if (grille[lignes - 1][j] == 1) marquerNonIsole(grille, lignes - 1, j);
}
int total = 0;
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
if (grille[i][j] == 1) {
total += calculerSurface(grille, i, j);
}
}
}
System.out.println(total);
}
private static void marquerNonIsole(int[][] grille, int x, int y) {
if (x < 0 || x >= grille.length || y < 0 || y >= grille[0].length || grille[x][y] != 1) return;
grille[x][y] = 2; // Marquer comme non isolé
for (int[] dir : DIRECTIONS) {
marquerNonIsole(grille, x + dir[0], y + dir[1]);
}
}
private static int calculerSurface(int[][] grille, int x, int y) {
if (x < 0 || x >= grille.length || y < 0 || y >= grille[0].length || grille[x][y] != 1) return 0;
grille[x][y] = 0;
int surface = 1;
for (int[] dir : DIRECTIONS) {
surface += calculerSurface(grille, x + dir[0], y + dir[1]);
}
return surface;
}
}
Problème 3 : Noyade des îles isolées
Énoncé : Transformer toutes les cellules des îles isolées (1) en eau (0).
Approche : Identifier les îles non isolées en les marquant avec une valeur temporaire (2), puis transformer les 1 restants en 0 et rétablir les 2 en 1.
import java.util.Scanner;
public class NoyerIles {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner lecteur = new Scanner(System.in);
int lignes = lecteur.nextInt();
int colonnes = lecteur.nextInt();
int[][] grille = new int[lignes][colonnes];
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
grille[i][j] = lecteur.nextInt();
}
}
for (int i = 0; i < lignes; i++) {
if (grille[i][0] == 1) marquerBord(grille, i, 0);
if (grille[i][colonnes - 1] == 1) marquerBord(grille, i, colonnes - 1);
}
for (int j = 0; j < colonnes; j++) {
if (grille[0][j] == 1) marquerBord(grille, 0, j);
if (grille[lignes - 1][j] == 1) marquerBord(grille, lignes - 1, j);
}
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
if (grille[i][j] == 1) grille[i][j] = 0;
else if (grille[i][j] == 2) grille[i][j] = 1;
}
}
// Afficher la grille modifiée
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
System.out.print(grille[i][j] + (j == colonnes - 1 ? "" : " "));
}
System.out.println();
}
}
private static void marquerBord(int[][] grille, int x, int y) {
if (x < 0 || x >= grille.length || y < 0 || y >= grille[0].length || grille[x][y] != 1) return;
grille[x][y] = 2;
for (int[] dir : DIRECTIONS) {
marquerBord(grille, x + dir[0], y + dir[1]);
}
}
}
Problème 4 : Problème du flux d'eau
Énoncé : Étant donné une grille de hauteurs, identifier les cellules dont l'eau peut s'écouler vers les bords supérieur/gauche et inférieur/droite.
Approche : Utiliser la recherche inverse à partir des bords pour marquer les cellules accessibles, puis trouver l'intersection.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class FluxEau {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner lecteur = new Scanner(System.in);
int lignes = lecteur.nextInt();
int colonnes = lecteur.nextInt();
int[][] hauteurs = new int[lignes][colonnes];
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
hauteurs[i][j] = lecteur.nextInt();
}
}
boolean[][] accessibleBord1 = new boolean[lignes][colonnes];
boolean[][] accessibleBord2 = new boolean[lignes][colonnes];
// Exploration depuis les bords supérieur et gauche
for (int i = 0; i < lignes; i++) parcourirInverse(hauteurs, accessibleBord1, i, 0);
for (int j = 0; j < colonnes; j++) parcourirInverse(hauteurs, accessibleBord1, 0, j);
// Exploration depuis les bords inférieur et droit
for (int i = 0; i < lignes; i++) parcourirInverse(hauteurs, accessibleBord2, i, colonnes - 1);
for (int j = 0; j < colonnes; j++) parcourirInverse(hauteurs, accessibleBord2, lignes - 1, j);
// Trouver l'intersection
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
if (accessibleBord1[i][j] && accessibleBord2[i][j]) {
System.out.println(i + " " + j);
}
}
}
}
private static void parcourirInverse(int[][] hauteurs, boolean[][] accessible, int x, int y) {
if (accessible[x][y]) return;
accessible[x][y] = true;
for (int[] dir : DIRECTIONS) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < hauteurs.length && ny >= 0 && ny < hauteurs[0].length
&& hauteurs[nx][ny] >= hauteurs[x][y]) {
parcourirInverse(hauteurs, accessible, nx, ny);
}
}
}
}
Problème 5 : Construire la plus grande île
Énoncé : En changeant au plus une cellule d'eau en terre, trouver la superficie maximale possible d'une île.
Approche : Identifier les îles avec des identifiants uniques, puis pour chaque cellule d'eau, calculer la superficie totale en connectant les îles adjacetnes.
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class PlusGrandeIle {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public static void main(String[] args) {
Scanner lecteur = new Scanner(System.in);
int lignes = lecteur.nextInt();
int colonnes = lecteur.nextInt();
int[][] grille = new int[lignes][colonnes];
boolean[][] visite = new boolean[lignes][colonnes];
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
grille[i][j] = lecteur.nextInt();
}
}
Map<integer integer=""> aires = new HashMap<>();
int identifiant = 2;
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
if (grille[i][j] == 1 && !visite[i][j]) {
int aire = marquerIle(grille, visite, i, j, identifiant);
aires.put(identifiant, aire);
identifiant++;
}
}
}
int maxSurface = 0;
for (int i = 0; i < lignes; i++) {
for (int j = 0; j < colonnes; j++) {
if (grille[i][j] == 0) {
Set<integer> ilesAdjacentes = new HashSet<>();
int surfacePotentielle = 1;
for (int[] dir : DIRECTIONS) {
int nx = i + dir[0];
int ny = j + dir[1];
if (nx >= 0 && nx < lignes && ny >= 0 && ny < colonnes && grille[nx][ny] > 1) {
int id = grille[nx][ny];
if (ilesAdjacentes.add(id)) {
surfacePotentielle += aires.get(id);
}
}
}
maxSurface = Math.max(maxSurface, surfacePotentielle);
}
}
}
// Cas où la grille est entièrement terrestre
if (maxSurface == 0) maxSurface = lignes * colonnes;
System.out.println(maxSurface);
}
private static int marquerIle(int[][] grille, boolean[][] visite, int x, int y, int id) {
if (x < 0 || x >= grille.length || y < 0 || y >= grille[0].length || grille[x][y] != 1 || visite[x][y]) return 0;
visite[x][y] = true;
grille[x][y] = id;
int aire = 1;
for (int[] dir : DIRECTIONS) {
aire += marquerIle(grille, visite, x + dir[0], y + dir[1], id);
}
return aire;
}
}
</integer></integer>