fork(2) download
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int check(int row, int col, char** lab, int** visited, queue<int>& plan){//находим количество стен рядом с каждой клеткой
  6. int empty = 0;//пустые клетки
  7. if(!visited[row][col]){
  8. if(lab[row+1][col]=='.'){//проверяем нижнюю клетку
  9. empty++;
  10. if(!visited[row+1][col]){
  11. plan.push(row+1);
  12. plan.push(col);
  13. }
  14. }
  15. if(lab[row-1][col]=='.'){//проверяем верхнюю клетку
  16. empty++;
  17. if(!visited[row-1][col]){
  18. plan.push(row-1);
  19. plan.push(col);
  20. }
  21. }
  22. if(lab[row][col+1]=='.'){//проверяем правую клетку
  23. empty++;
  24. if(!visited[row][col+1]){
  25. plan.push(row);
  26. plan.push(col+1);
  27. }
  28. }
  29. if(lab[row][col-1]=='.'){//проверяем левую клетку
  30. empty++;
  31. if(!visited[row][col-1]){
  32. plan.push(row);
  33. plan.push(col-1);
  34. }
  35. }
  36. visited[row][col]=1;//отмечаем, что клетка пройдена
  37. return 4-empty;//количество стен рядом с клеткой
  38. }
  39. return 0;
  40. }
  41.  
  42. int main() {
  43. int N;
  44. cin >> N;
  45. char** lab = new char* [N+2];
  46. int** visited = new int * [N+2];
  47. for(int i=0; i<N+2; i++){
  48. lab[i] = new char [N+2];
  49. visited[i] = new int [N+2];
  50. for(int j=0; j<N+2; j++){
  51. visited[i][j] = 0;//массив для проверки посещённости клеток
  52. if(i==0||i==N+1||j==0||j==N+1){
  53. lab[i][j]='*';//вокруг данного лабиринта делаем стену
  54. } else {
  55. cin >> lab[i][j];//данный лабиринт
  56. }
  57. }
  58. }
  59. queue <int> plan;
  60. plan.push(1);//начинаем считать с левой верхней клетки
  61. plan.push(1);
  62. int walls=0;
  63. while(!plan.empty()){
  64. int row=plan.front();
  65. plan.pop();
  66. int col=plan.front();
  67. plan.pop();
  68. walls+=check(row, col, lab, visited, plan);
  69. }
  70. if(!visited[N][N]){//если не попали в правую нижнюю клетку
  71. plan.push(N);//считаем начиная с неё
  72. plan.push(N);
  73. while(!plan.empty()){
  74. int row=plan.front();
  75. plan.pop();
  76. int col=plan.front();
  77. plan.pop();
  78. walls+=check(row, col, lab, visited, plan);
  79. }
  80. }
  81. walls-=4;//стены у левого верхнего и правого нижнего угла отсутствуют
  82. int meters=walls*9;
  83. cout << meters << endl;
  84. return 0;
  85. }
Success #stdin #stdout 0s 3280KB
stdin
5
.....
...##
..#..
..###
.....
stdout
198