Problème de grille

Énoncé

Étant donné une grille de dimension n×m, avec c cellules supprimées.

• Deux cellules sont adjacentes si elles partagent une arête commune.
• Deux cellules sont connectées si elles sont adjacentes ou s'il existe une chaîne de cellules adjacentes les reliant.

Objectif : supprimer le minimum de cellules supplémentaires pour qu'il existe au moins deux cellules non connectées. Déterminer si c'est possible et, dans l'affirmative, minimiser le nombre de suppressions.

Solution

Propriété clé

On observe que la réponse est bornée par 2 (ans ≤ 2).

Preuve : Si une cellule se trouve dans l'un des quatre coins, la propriété est évidente. Sinon, s'il existe une cellule sur un bord (hors extrémités) avec degré 3, alors au moins une cellule adjacente à cette cellule a été supprimée. Si aucune de ces conditions n'est remplie, on peut itérer sur une région réduite.

Ceci illustre une technique importante : considérer la bornne supérieure de la réponse.

Cas sans solution (-1)

Deux cas mènent à l'impossibilité :

• Moins de deux cellules initialement présentes (n×m - c < 2).
• Exactement deux cellules initialement présentes et adjacentes (vérifié après calcul si ans ≠ 0 et n×m - c = 2).

Cas ans = 0

Si le graphe formé par les cellules restantes (connectées par arêtes communes) est déjà déconnecté, alors aucune suppression supplémentaire n'est nécessaire (ans = 0).

Cas ans = 1 (approche générale)

Le graphe possède un point de coupure. On peut utiliser l'algorithme de Tarjan pour détecter les points de coupure. Cependant, la grille peut être très grande (N ≤ 10^5, M ≤ 2×10^5), donc une construction directe du graphe est impraticable.

On exploite le fait que seules les cellules dans un voisinage local autour des suppressions sont pertinentes. Pour chaque cellule supprimée, on considère un bloc 5×5 de cellules. Les cellules immédiatement adjacentes (connexion de niveau 1) sont candidates pour les points de coupure, tandis que les cellules plus éloignées (connexion de niveau 2) sont incluses pour assurer la complétude du graphe.

On effectue un BFS pour identifier les cellules effectives, on les réindexe discrètement pour construire un graphe. On évite les arêtes doublées en connectant chaque cellule uniquement vers la droite et vers le bas.

Après l'algorithme de Tarjan, si le compteur de timestamps (DFN) est inférieur au nombre total de points, le graphe est initialement déconnecté (ans = 0). S'il existe un point de coupure de connexion de niveau 1, alors ans = 1.

Sinon, par défaut, ans = 2.

Implémentation

L'algorithme utilise une recherche en largeur (BFS) et l'algorithme de Tarjan pour les points de coupure. Les coordonnées sont gérées via une discrétisation avec des maps pour éviter une consommation excessive de mémoire.

// Exemple de code restructuré
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> Coord;
const int MAX_POINTS = 5000010;

vector<int> adj[MAX_POINTS];
int timestamp[MAX_POINTS], lowlink[MAX_POINTS], cutCount[MAX_POINTS];
int totalPoints, counter, result;
map<Coord, int> pointToId;
vector<Coord> idToPoint;
set<Coord> removedCells;
bool isLevel1[MAX_POINTS];

void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void findCutPoints(int u, int parent) {
    timestamp[u] = lowlink[u] = ++counter;
    int childCount = 0;
    for (int v : adj[u]) {
        if (!timestamp[v]) {
            childCount++;
            findCutPoints(v, u);
            lowlink[u] = min(lowlink[u], lowlink[v]);
            if ((parent != -1 && lowlink[v] >= timestamp[u]) || (parent == -1 && childCount > 1)) {
                if (isLevel1[u]) result = min(result, 1);
            }
        } else if (v != parent) {
            lowlink[u] = min(lowlink[u], timestamp[v]);
        }
    }
}

void processRegion(Coord start) {
    // Réinitialisation des structures
    for (int i = 1; i <= totalPoints; i++) adj[i].clear();
    pointToId.clear();
    idToPoint.clear();
    totalPoints = counter = 0;

    queue<Coord> bfsQueue;
    set<Coord> visited;
    bfsQueue.push(start);
    visited.insert(start);

    while (!bfsQueue.empty()) {
        Coord current = bfsQueue.front(); bfsQueue.pop();
        for (int dx = -2; dx <= 2; dx++) {
            for (int dy = -2; dy <= 2; dy++) {
                Coord neighbor = {current.first + dx, current.second + dy};
                if (neighbor.first < 1 || neighbor.first > n || neighbor.second < 1 || neighbor.second > m) continue;
                if (removedCells.count(neighbor)) {
                    if (!visited.count(neighbor)) {
                        visited.insert(neighbor);
                        bfsQueue.push(neighbor);
                    }
                } else {
                    if (!pointToId.count(neighbor)) {
                        pointToId[neighbor] = ++totalPoints;
                        idToPoint.push_back(neighbor);
                        isLevel1[totalPoints] = (max(abs(dx), abs(dy)) < 2);
                    }
                }
            }
        }
    }

    // Construction du graphe
    for (int i = 1; i <= totalPoints; i++) {
        Coord p = idToPoint[i-1];
        Coord right = {p.first + 1, p.second};
        if (pointToId.count(right)) addEdge(i, pointToId[right]);
        Coord down = {p.first, p.second + 1};
        if (pointToId.count(down)) addEdge(i, pointToId[down]);
    }

    findCutPoints(1, -1);
    if (counter < totalPoints) result = min(result, 0);
}

int main() {
    // Lecture et traitement des entrées
    // Appels à processRegion pour chaque composante connexe de cellules supprimées
    // Gestion des cas particuliers (grille 1D, etc.)
    return 0;
}

Problème Single Cut of Failure

Solution

Ce problème est plus simple. L'idée est d'utiliser la borne supérieure de la réponse. En traçant les diagonales du rectangle, la réponse maximale est 2. Il suffit donc de vérifier si une réponse de 1 est possible.

Une réponse de 1 est possible s'il existe une ligne droite qui intersecte tous les segments donnés. On transforme le contour du rectangle en une ligne droite, où chaque segment correspond à un intervalle sur cette ligne. Le problème revient alors à déterminer s'il existe un point qui est inclus dans exactement un des deux extrémités de chaque segment. On utilise une technique de pointeur coulissant (double pointeur) avec un tableau de comptage.

Implémentation

// Exemple de code restructuré
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_SEGMENTS = 5e6 + 10;
int width, height, numSegments;
vector<int> endpoints;

int coordinateToPosition(int x, int y) {
    if (y == 0) return x;
    if (x == width) return width + y;
    if (y == height) return 2 * width + height - x;
    if (x == 0) return 2 * width + 2 * height - y;
    return 0;
}

void printPoint(int pos) {
    if (pos <= width) printf("%.1lf %.1lf", pos * 0.5, 0.0);
    else if (pos <= width + height) printf("%.1lf %.1lf", width * 0.5, (pos - width) * 0.5);
    else if (pos <= 2 * width + height) printf("%.1lf %.1lf", (2 * width + height - pos) * 0.5, height * 0.5);
    else printf("%.1lf %.1lf", 0.0, (2 * width + 2 * height - pos) * 0.5);
}

int main() {
    // Lecture des segments et conversion des positions
    // Tri et compression des coordonnées
    // Pointeur coulissant pour chercher une solution de type 1
    // Sinon, sortie par défaut pour une solution de type 2
    return 0;
}