7024. Красное и черное

Есть прямоугольная комната, покрытая квадратными плитками. Каждая плитка окрашена в красный или черный цвет. Человек стоит на черной плитке. Из текущей плитки он может перейти на одну из четырех соседних плиток. Но он не может наступать на красные плитки, двигаться разрешено только по черным.

Вычислите количество черных плиток, которые можно достичь описанными передвижениями.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит два натуральных числа w и h (w, h ≤ 20) – количество плиток по x- и y-направлению.

Каждая из следующих h строк содержит по w символов. Каждый символ задает цвет плитки следующим образом:

· '.' - черная плитка;

· '#' - красная плитка;

· '@' – человек на черной плитке (символ присутствует в каждом тесте только один раз);

Последняя строка содержит два нуля.

Выход. Для каждого теста вывести в отдельной строке количество достижимых плиток (включая начальную).

Пример входа	Пример выхода
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0	45 59 6 13

РЕШЕНИЕ

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

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

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

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

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

#define MAX 22

char m[MAX][MAX];

Функция dfs реализует поиск в глубину из точки (i, j).

void dfs(int i, int j)

{

Если координаты точки выходят за границы комнаты, то завершаем поиск.

if ((i < 0) || (i >= h) || (j < 0) || (j >= w)) return;

Если в клетке (i, j) находится не черная плитка, то также завершаем поиск.

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

Иначе помечаем клетку пройденной (считаем например что в ней появляется красная плитка), увеличиваем число пройденных клеток c на 1.

m[i][j] = '#'; c++;

Далее идем влево в (i, j – 1), вправо в (i, j + 1), вверх в (i – 1, j) и вниз в (i + 1, j).

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

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

}

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

while(scanf("%d %d\n",&w,&h), w + h)

{

for(с = i = 0; i < h; i++) gets(m[i]);

Ищем плитку, на которой стоит человек. Запускаем из нее поиск в глубину.

for(i = 0; i < h; i++)

for(j = 0; j < w; j++)

if (m[i][j] == '@') dfs(i,j);

Выводим количество достижимых плиток.

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

}

Java реализация

import java.util.*;

//import java.io.*;

public class Main

{

static char m[][];

static int h, w, c;

static void dfs(int i, int j)

{

if ((i < 0) || (i >= h) || (j < 0) || (j >= w)) return;

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

m[i][j] = '#'; c++;

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 ("7024.in"));

while(true)

{

w = con.nextInt();

h = con.nextInt();

if (w == 0 && h == 0) break;

c = 0;

m = new char[h][w];

for(int i = 0; i < h; i++)

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

for(int i = 0; i < h; i++)

for(int j = 0; j < w; j++)

if (m[i][j] == '@') dfs(i,j);

System.out.println(c);

}

con.close();

}

}