v 0. Pasted by slipstak2 as cpp at 2010-11-23 23:07:46 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 6.
  2. // 6F. Покраска лабиринта [paintlab]
  3. // Рекурсивный DFS.
  4. // ibelyaev: 23Nov2010
  5.  
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <vector>
  9. #include <cstring>
  10. #include <string.h>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <queue>
  14.  
  15. using namespace std;
  16.  
  17. int n;
  18. const int max_size = 36;
  19. char mas[max_size][max_size];
  20. void input()
  21. {
  22.     scanf("%d\n",&n);
  23.     char c;
  24.     for (int i=1;i<=n;i++)
  25.     {
  26.         for (int j=1;j<=n;j++)
  27.         {
  28.             scanf("%c",&c);
  29.             mas[i][j] = c;
  30.         }
  31.         scanf("%c",&c); // считываем "\n"
  32.     }
  33.     for (int i=0;i<n+2;i++)
  34.     {
  35.         mas[0][i] = mas[n+1][i] = '#';
  36.         mas[i][0] = mas[i][n+1] = '#';
  37.     }
  38. }
  39. struct state
  40. {
  41.     int x,y,pos;
  42.     state(int X, int Y, int Pos)
  43.     {
  44.         x = X;  // координата X клетки
  45.         y = Y;  // координата Y клетки
  46.         pos = Pos; // позиция в массиве движения, с которой нужно продолжать
  47.     }
  48. };
  49. int moveX[4] = {0,1,0,-1};
  50. int moveY[4] = {1,0,-1,0};
  51. // Рекурсивный поиск в глубину
  52. void DFS(int x, int y, int &walls)
  53. {
  54.     if (mas[x][y] == '.')
  55.         mas[x][y] = 'X';
  56.     else
  57.         return;
  58.     for (int i=0;i<4;i++)
  59.     {
  60.         int nextX = x + moveX[i];
  61.         int nextY = y + moveY[i];
  62.         if (mas[nextX][nextY] == '#')
  63.             walls++;
  64.     }
  65.     for (int i=0;i<4;i++)
  66.     {
  67.         int nextX = x + moveX[i];
  68.         int nextY = y + moveY[i];
  69.         if (mas[nextX][nextY] == '.')
  70.             DFS(nextX,nextY,walls);
  71.     }
  72. }
  73. void solve()
  74. {
  75.     int walls = 0;
  76.     DFS(1,1,walls);
  77.     DFS(n,n,walls);
  78.     cout<<(walls-4) * 9;
  79. }
  80. // for debug only
  81. void output()
  82. {
  83.     cout<<endl;
  84.     for (int i=0;i<n+2;i++)
  85.     {
  86.         for (int j=0;j<n+2;j++)
  87.             cout<<mas[i][j];
  88.         cout<<endl;
  89.     }
  90. }
  91. int main()
  92. {
  93.     freopen("input.txt","r",stdin);
  94.     freopen("output.txt","w",stdout);
  95.    
  96.     input();
  97.     solve();
  98.     //output();
  99.     return 0;
  100. }


Editing is locked.