v 0. Pasted by slipstak2 as cpp at 2010-11-23 23:05:27 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.     stack<state> s;
  55.     if (mas[x][y] == '.')
  56.     {
  57.         s.push(state(x,y,0));
  58.         mas[x][y] = 'X';
  59.     }
  60.     while (!s.empty())
  61.     {
  62.         // считаем количество стенок
  63.         if (s.top().pos == 0)
  64.         {
  65.             for (int i=0;i<4;i++)
  66.             {
  67.                 int x = s.top().x + moveX[i];
  68.                 int y = s.top().y + moveY[i];
  69.                 if (mas[x][y] == '#')
  70.                     walls++;
  71.             }
  72.         }
  73.         for (int i=s.top().pos; i<4; i++)
  74.         {
  75.             int x = s.top().x + moveX[i];
  76.             int y = s.top().y + moveY[i];
  77.             s.top().pos++;
  78.             if (mas[x][y] == '.')
  79.             {
  80.                 mas[x][y] = 'X';
  81.                 s.push(state(x,y,0));
  82.                 break;
  83.             }
  84.         }
  85.         // Вершина стека отработана
  86.         if (s.top().pos == 4)
  87.             s.pop();
  88.     }   
  89. }
  90. void solve()
  91. {
  92.     int walls = 0;
  93.     DFS(1,1,walls);
  94.     DFS(n,n,walls);
  95.     cout<<(walls-4) * 9;
  96. }
  97. // for debug only
  98. void output()
  99. {
  100.     cout<<endl;
  101.     for (int i=0;i<n+2;i++)
  102.     {
  103.         for (int j=0;j<n+2;j++)
  104.             cout<<mas[i][j];
  105.         cout<<endl;
  106.     }
  107. }
  108. int main()
  109. {
  110.     freopen("input.txt","r",stdin);
  111.     freopen("output.txt","w",stdout);
  112.    
  113.     input();
  114.     solve();
  115.     //output();
  116.     return 0;
  117. }


Editing is locked.