4001. Area of the room

Find the area of the room in the square labyrinth.

Input. The first line contains the size n (3 ≤ n ≤ 10) of labyrinth. Each of the next n lines contains n characters describing the labyrinth (symbol "." denotes the empty cell, symbol "*" denotes the wall). The last line contains two numbers – the row and column numbers for the cell that locates in the room which area should be found. It is guaranteed that this cell is empty and the labyrinth is surrounded by walls from all sides. The rows and columns of the labyrinth are numbered starting from one.

Output. Print the number of empty cells in a given room.

Sample input	Sample output
5 ***** **..* *.*.* *..** ***** 2 4	3

SOLUTION

graphs – dfs - grids

Algorithm analysis

Start depth search from the given cell in the room. Thus, we’ll go through all the empty cells of the room, which number should be counted.

Algorithm realization

The given maze will be stored in a two dimensional character array m.

#define MAX 12

char m[MAX][MAX];

The dfs function starts depth first search from the point (i, j). If there is a wall in it, complete the search. Otherwise, mark the cell passed (put a wall into it) and try to go left to (i, j – 1), right to (i, j + 1), up to (i – 1, j) and down to (i + 1, j).

void dfs(int i, int j)

{

if (m[i][j] == '*') return;

cnt++;

m[i][j] = '*';

dfs(i-1,j); dfs(i+1,j);

dfs(i,j-1); dfs(i,j+1);

}

The main part of the program. Read the maze into the two dimensional character array m.

scanf("%d\n",&n);

for(i = 1; i <= n; i++) gets(m[i]+1);

Start depth first search from the given position. In the variable cnt count the number of empty cells in the room.

scanf("%d %d",&i,&j);

cnt = 0; dfs(i,j);

Print the answer.

printf("%d\n",cnt);

Java realization

import java.util.*;

//import java.io.*;

public class Main

{

static char m[][];

static int cnt = 0;

static void dfs(int i, int j)

{

if (m[i][j] == '*') return;

cnt++;

m[i][j] = '*';

dfs(i-1,j); dfs(i+1,j);

dfs(i,j-1); dfs(i,j+1);

}

public static void main(String[] args) //throws IOException

{

Scanner con = new Scanner(System.in);

//Scanner con = new Scanner(new FileReader ("4001.in"));

int n = con.nextInt();

// upper left corner of array is (1, 1)

m = new char[n+1][n];

for(int i = 1; i <= n; i++)

m[i] = ("*" + con.next()).toCharArray();

int i = con.nextInt();

int j = con.nextInt();

dfs(i,j);

System.out.println(cnt);

con.close();

}

}