4001. Площадь комнаты

Вычислить площадь комнаты в квадратном лабиринте.

Вход. В первой строке находится размер лабиринта n (3 ≤ n ≤ 10). Каждая из следующих n строк содержит по n символов, задающих лабиринт (символ "." обозначает пустую клетку, а "*" – стенку). Последняя строка содержит два числа – номер строки и столбца клетки, находящейся в комнате, площадь которой необходимо вычислить. Гарантируется, что эта клетка пустая и лабиринт окружен стенками со всех сторон. Строки и столбцы лабиринта нумеруются с единицы.

Выход. Вывести количество пустых клеток в данной комнате.

Пример входа	Пример выхода
5 ***** **..* *.*.* *..** ***** 2 4	3

РЕШЕНИЕ

поиск в глубину

Анализ алгоритма

Организуем поиск в глубину из заданной клетки в комнате. Таким образом мы пройдем по всем пустым клеткам комнаты, количество которых и следует подсчитать.

Реализация алгоритма

Заданный лабиринт будем хранить в двумерном символьном массиве m.

#define MAX 12

char m[MAX][MAX];

Функция dfs запускает поиск в глубину из точки (i, j). Если в ней находится стена, то завершаем поиск. Иначе помечаем клетку пройденной (ставим в ней стену), после чего стараемся пойти влево в (i, j – 1), вправо в (i, j + 1), вверх в (i – 1, j) и вниз в (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);

}

Основная часть программы. Читаем лабиринт в двумерный символьный массив m.

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

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

Запускаем поиск в глубину, начиная с заданной позиции. В переменной cnt подсчитываем количество пустых клеток в комнате.

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

cnt = 0; dfs(i,j);

Выводим ответ.

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

Java реализация

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();

}

}