ACM/ICPC Indonesia National Contest 2008

Problem D. Maze Walker

Deskripsi Soal D
Problem Author: Suhendry Effendy

Diberikan sebuah maze, anda diminta untuk menghitung ada berapa banyak pasang cell yang terhubung (ada jalan dari cell yang satu ke cell yang lain).

Untuk menyelesaikan soal ini kita perlu melakukan flood fill pada maze dan menghitung jumlah cell untuk setiap area tertutup. Untuk setiap area tertutup, jumlah pasangan cell yang terhubung bisa dihitung dengan rumus N * (N - 1)/2. Rumus yang sama yang digunakan untuk menjawab pertanyaan klasik: "ada berapa jabat tangan yang terjadi pada ruangan dengan N orang".

Berikut adalah data dan penjelasan dari sample input-2:

No.	Pasangan	Path
1	A - B	A - B
2	A - C	A - B - C
3	A - D	A - B - C - D
4	B - C	B - C
5	B - D	B - C - D
6	C - D	C - D
7	F - G	F - G
8	F - J	F - G - J
9	G - J	G - J
10	H - I	H - I

Proses labeling semua cell dengan flood fill bisa dilakukan dengan kompleksitas O(N²) baik menggunakan BFS/Breath First Search ataupun DFS/Depth First Search (rekursi atau stack). Dengan sedikit modifikasi kita bisa mengubah program flood fill agar juga menghitung jumlah cell yang di fill pada suatu area tertutup. Sehingga total kompleksitas waktu yang diperlukan tetap O(N²).

Solusi C/C++
oleh Suhendry Effendy

#include <stdio.h>

int R, C;
char A[101][101];
int pr[] = {0, 0, -1, 1};
int pc[] = {-1, 1, 0, 0};

int fill(int r, int c) {
  int ret = 1;
  A[r][c] = '#';
  for ( int i = 0; i < 4; i++ ) {
    int tr = r + pr[i];
    int tc = c + pc[i];
    if ( 0 <= tr && tr < R && 0 <= tc && tc < C && A[tr][tc] == '.' )
      ret += fill(tr,tc);
  }
  return ret;
}

int main()
{
  int T;
  scanf( "%d", &T );

  while ( T-- > 0 ) {
    scanf( "%d %d", &R, &C );
    for ( int i = 0; i < R; i++ )
      scanf( "%s", A[i] );

    int ans = 0;
    for ( int i = 0; i < R; i++ )
      for ( int j = 0; j < C; j++ )
        if ( A[i][j] == '.' ) {
          int p = fill(i,j);
          ans += p * (p - 1) / 2;
        }

    printf( "%d\n", ans );
  }

  return 0;
}

Solusi JAVA
oleh Felix Halim

import java.util.*;

public class maze {
  public static long ff(char[][] m, int r, int c){
    if (r<0 || r>=m.length) return 0;
    if (c<0 || c>=m[0].length) return 0;
    if (m[r][c]!='.') return 0;

    long ret = 1;
    m[r][c] = '#';
    ret += ff(m,r+1,c);
    ret += ff(m,r-1,c);
    ret += ff(m,r,c+1);
    ret += ff(m,r,c-1);
    return ret;
  }

  void solve(){
    Scanner scan = new Scanner(System.in);

    int nTC = scan.nextInt();
    while (nTC-- > 0){
      int R = scan.nextInt();
      int C = scan.nextInt();

      char[][] m = new char[R][];
      for (int i=0; i<R; i++)
        m[i] = scan.next().toCharArray();

      long res = 0;
      for (int i=0; i<R; i++)
        for (int j=0; j<C; j++)
          if (m[i][j]=='.'){
            long c = ff(m,i,j);
            res += (c*(c-1))/2;
          }

      System.out.println(res);
    }
  }

  public static void main(String[] args){
    new maze().solve();
  }
}

Ketika menjalankan solusi JAVA dari Felix Halim anda perlu memperbesar stack-memory yang digunakan menjadi 32M (sesuai dengan setting yang digunakan oleh juri). Caranya:

java -Xss32m maze

Jika stack-memory tidak diperbesar maka program di atas akan crash (run-time error) karena memory yang diperlukan oleh proses rekursifnya tidak cukup.