1 /*
2 * File: Timus 1033. Labyrinth
3 * Author: xiaotian @ hnu
4 * Created on 2010年9月29日, 上午10:30
5 * 题解：bfs数墙面个数，最后乘以 9 。
6 */
7
8 #include<stdio.h>
9 #include<iostream>
10 #include<string.h>
11 #include<queue>
12 #include<set>
13 #include<math.h>
14 using namespace std;
15 #define N 40
16 #define inf 0x7ffffff
17 const int dx[4] = {0, 1, 0, -1};
18 const int dy[4] = {1, 0, -1, 0};
19 char map[N][N];
20 int vis[N][N][4];
21 int num[N][N];
22 int n;
23
24 struct point {
25 int x, y;
26 point(int xx = 0, int yy = 0) : x(xx), y(yy) {
27 }
28 };
29
30 inline int ok(int x, int y) {
31 return x > 0 && x <= n && y > 0 && y <= n;
32 }
33
34 int bfs(point s) {
35 int ans = 0;
36 queue<point>q;
37 q.push(s);
38 num[s.x][s.y] = 1;
39 while (!q.empty()) {
40 point p = q.front();
41 q.pop();
42 for (int i = 0; i < 4; i++) {
43 int x = p.x + dx[i], y = p.y + dy[i];
44 if ((x == 0 || x == n + 1 || y == 0 || y == n + 1 || map[x][y] == '#') && vis[p.x][p.y][i] == 0 && vis[x][y][(i + 2) % 4] == 0) {
45 ans++;
46 vis[p.x][p.y][i] = 1;
47 vis[x][y][(i + 2) % 4] = 1;
48 }
49 if (ok(x, y) && map[x][y] == '.' && num[x][y] == 0) {
50 num[x][y] = 1;
51 q.push(point(x, y));
52 }
53 }
54 }
55 return ans;
56 }
57
58 int main() {
59 while (scanf("%d\n", &n) != EOF) {
60 for (int i = 1; i <= n; i++)
61 gets(map[i] + 1);
62 for (int i = 0; i <= n + 2; i++)
63 for (int j = 0; j <= n + 2; j++) {
64 num[i][j] = 0;
65 for (int k = 0; k < 4; k++)
66 vis[i][j][k] = 0;
67 }
68 int ans=bfs(point(1,1))+bfs(point(n,n));
69 printf("%d\n", ans*9-36);
70 }
71 return 0;
72 }