Paste will expire never.
- // Меньшиков. Тренировка 6.
- // 6F. Покраска лабиринта [paintlab]
- // Нерекурсивный DFS.
- // ibelyaev: 23Nov2010
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <cstring>
- #include <string.h>
- #include <algorithm>
- #include <stack>
- #include <queue>
- using namespace std;
- int n;
- const int max_size = 36;
- char mas[max_size][max_size];
- void input()
- {
- scanf("%d\n",&n);
- char c;
- for (int i=1;i<=n;i++)
- {
- for (int j=1;j<=n;j++)
- {
- scanf("%c",&c);
- mas[i][j] = c;
- }
- scanf("%c",&c); // считываем "\n"
- }
- for (int i=0;i<n+2;i++)
- {
- mas[0][i] = mas[n+1][i] = '#';
- mas[i][0] = mas[i][n+1] = '#';
- }
- }
- struct state
- {
- int x,y,pos;
- state(int X, int Y, int Pos)
- {
- x = X; // координата X клетки
- y = Y; // координата Y клетки
- pos = Pos; // позиция в массиве движения, с которой нужно продолжать
- }
- };
- int moveX[4] = {0,1,0,-1};
- int moveY[4] = {1,0,-1,0};
- // Нерекурсивный поиск в глубину (первый опыт :))
- void DFS(int x, int y, int &walls)
- {
- stack<state> s;
- if (mas[x][y] == '.')
- {
- s.push(state(x,y,0));
- mas[x][y] = 'X';
- }
- while (!s.empty())
- {
- // считаем количество стенок
- if (s.top().pos == 0)
- {
- for (int i=0;i<4;i++)
- {
- int x = s.top().x + moveX[i];
- int y = s.top().y + moveY[i];
- if (mas[x][y] == '#')
- walls++;
- }
- }
- for (int i=s.top().pos; i<4; i++)
- {
- int x = s.top().x + moveX[i];
- int y = s.top().y + moveY[i];
- s.top().pos++;
- if (mas[x][y] == '.')
- {
- mas[x][y] = 'X';
- s.push(state(x,y,0));
- break;
- }
- }
- // Вершина стека отработана
- if (s.top().pos == 4)
- s.pop();
- }
- }
- void solve()
- {
- int walls = 0;
- DFS(1,1,walls);
- DFS(n,n,walls);
- cout<<(walls-4) * 9;
- }
- // for debug only
- void output()
- {
- cout<<endl;
- for (int i=0;i<n+2;i++)
- {
- for (int j=0;j<n+2;j++)
- cout<<mas[i][j];
- cout<<endl;
- }
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- //output();
- return 0;
- }
Editing is locked.