Задача e-olimp 1061.
Лабиринт представляет собой квадрат, состоящий из N×N сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесен снизу, сверху, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри. Помогите ему рассчитать количество краски, необходимой для этого.
Входные данные
В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решетка — сегмент со стеной.
3 ≤ N ≤ 33, размер сегмента 3×3, высота стен 3 метра.
Выходные данные
Вывести одно число — площадь видимой части внутренних стен лабиринта в квадратных метрах.
Пример
| Входные данные | Выходные данные |
| 5
. . . . . . . . # # . . # . . . . # # # . . . . . |
198 |
C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <queue> using namespace std; int check(int row, int col, char** lab, int** visited, queue<int>& plan){//находим количество стен рядом с каждой клеткой int empty = 0;//пустые клетки if(!visited[row][col]){ if(lab[row+1][col]=='.'){//проверяем нижнюю клетку empty++; if(!visited[row+1][col]){ plan.push(row+1); plan.push(col); } } if(lab[row-1][col]=='.'){//проверяем верхнюю клетку empty++; if(!visited[row-1][col]){ plan.push(row-1); plan.push(col); } } if(lab[row][col+1]=='.'){//проверяем правую клетку empty++; if(!visited[row][col+1]){ plan.push(row); plan.push(col+1); } } if(lab[row][col-1]=='.'){//проверяем левую клетку empty++; if(!visited[row][col-1]){ plan.push(row); plan.push(col-1); } } visited[row][col]=1;//отмечаем, что клетка пройдена return 4-empty;//количество стен рядом с клеткой } return 0; } int main() { int N; cin >> N; char** lab = new char* [N+2]; int** visited = new int * [N+2]; for(int i=0; i<N+2; i++){ lab[i] = new char [N+2]; visited[i] = new int [N+2]; for(int j=0; j<N+2; j++){ visited[i][j] = 0;//массив для проверки посещённости клеток if(i==0||i==N+1||j==0||j==N+1){ lab[i][j]='*';//вокруг данного лабиринта делаем стену } else { cin >> lab[i][j];//данный лабиринт } } } queue <int> plan; plan.push(1);//начинаем считать с левой верхней клетки plan.push(1); int walls=0; while(!plan.empty()){ int row=plan.front(); plan.pop(); int col=plan.front(); plan.pop(); walls+=check(row, col, lab, visited, plan); } if(!visited[N][N]){//если не попали в правую нижнюю клетку plan.push(N);//считаем начиная с неё plan.push(N); while(!plan.empty()){ int row=plan.front(); plan.pop(); int col=plan.front(); plan.pop(); walls+=check(row, col, lab, visited, plan); } } walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют int meters=walls*9; cout << meters << endl; return 0; } |
Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static int check(int row, int col, char [][] lab, int [][] visited, ArrayDeque <Integer> plan){//находим количество стен рядом с каждой клеткой int empty = 0;//пустые клетки if(visited[row][col]!=1){ if(lab[row+1][col]=='.'){//проверяем нижнюю клетку empty++; if(visited[row+1][col]!=1){ plan.offer(row+1); plan.offer(col); } } if(lab[row-1][col]=='.'){//проверяем верхнюю клетку empty++; if(visited[row-1][col]!=1){ plan.offer(row-1); plan.offer(col); } } if(lab[row][col+1]=='.'){//проверяем правую клетку empty++; if(visited[row][col+1]!=1){ plan.offer(row); plan.offer(col+1); } } if(lab[row][col-1]=='.'){//проверяем левую клетку empty++; if(visited[row][col-1]!=1){ plan.offer(row); plan.offer(col-1); } } visited[row][col]=1;//отмечаем, что клетка пройдена return 4-empty;//количество стен рядом с клеткой } return 0; } public static void main (String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); char [][] lab = new char [N+2][]; int [][] visited = new int [N+2][]; for(int i=0; i<N+2; i++){ lab[i] = new char [N+2]; visited[i] = new int [N+2]; for(int j=0; j<N+2; j++){ visited[i][j] = 0;//массив для проверки посещённости клеток if(i==0||i==N+1||j==0||j==N+1){ lab[i][j]='*';//вокруг данного лабиринта делаем стену } } } String line; for(int i=1; i<N+1; i++){ line = in.next(); for(int j=1; j<N+1; j++){ lab[i][j]=line.charAt(j-1);//заполняем лабиринт } } ArrayDeque <Integer> plan = new ArrayDeque<Integer>(); plan.offer(1);//начинаем считать с левой верхней клетки plan.offer(1); int walls=0; while(!plan.isEmpty()){ int row=plan.poll(); int col=plan.poll(); walls+=check(row, col, lab, visited, plan); } if(visited[N][N]!=1){//если не попали в правую нижнюю клетку plan.offer(N);//считаем начиная с неё plan.offer(N); while(!plan.isEmpty()){ int row=plan.poll(); int col=plan.poll(); walls+=check(row, col, lab, visited, plan); } } walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют int meters = walls * 9; System.out.println(meters); } } |
Для решения задачи я использовала алгоритм поиска в ширину: начиная с левой верхней клетки, которая гарантированно пуста, проверяю все смежные с ней и заношу их в план проверки. Для каждой клетки считаю количество пустых смежных клеток и получаю число стен рядом с ней. Чтобы было удобно проверять смежные клетки на пустоту, я сделала «стену» вокруг данного лабиринта. После проверки клетки отмечаю, что она просмотрена.
Так как в условии не гарантируется, что есть проход от левой верхней до правой нижней клетки, проверяю, посещена ли последняя. Если нет, снова запускаю поиск, начиная с неё.
Хорошее решение.
Эх, а Java решение не прошло на e-olymp, жаль. Все равно, 8 баллов начисляю.