迷宫的管理员们决定在新开始的季节里使用新的墙纸。出于这个目的他们需要一个程序来计算迷宫内墙壁的面积。这就是你即将要做的工作。
我们把这个迷宫用一个N*N (3 <= N <= 33) 的矩阵表示。一些矩阵单元包含一个 “ .” （这代表一个空的方块），另一些矩阵单元包含一个“ #” （这代表一个用巨石砌成的石墙占据的方块）。全部方块的大小都为 3*3 平方米。
墙壁由迷宫的四周（除了作为迷宫出入口的左上角和右下角以外）以及那些标记为“ #” 的矩阵单元构成，除此之外没有其他的墙。在输入的矩阵里左上角和右下角永远是一个“ .”。
你的任务是计算迷宫里可见部分的墙壁的面积。换句话说，就是对迷宫的游客来说墙壁表面可见的部分。注意在两块相邻的石块之间没有空隙，即使两块石块在转角处相接触，我们都认为它们是相邻的。看看图示的例子：迷宫中可见的墙壁都用加粗的线条来描画。所有墙壁的高度都是三米。
input：
输入的第一行包含一个数字N。接下来的N行每行都包含有N个字符。每行描述了迷宫矩阵的一行。每行都只有“ .” 、“ #” 这两个字符并都以一个换行符结束。输入里没有任何的空格。
output：
你的程序必须输出一个整数，即所需要的壁纸的准确面积。
input：
5
.....
...##
..#..
..###
.....
output：
198
【参考程序】：
#include<iostream>
using namespace std;
struct node
{
int x,y;
} list[1500];
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
char map[40][40];
bool bo[40][40];
int n,ans;
int main()
{
scanf("%d",&n);getchar();
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
scanf("%c",&map[i][j]);
getchar();
}
for (int i=1;i<=n;i++)
{
map[0][i]='#';map[i][0]='#';
map[i][n+1]='#';map[n+1][i]='#';
}
memset(bo,false,sizeof(bo));
bo[1][1]=bo[n][n]=true;
int head,tail,tx,ty;
head=1;tail=2;
list[1].x=1;list[1].y=1;
list[2].x=n;list[2].y=n;
ans=0;
while (head<=tail)
{
for (int i=0;i<=3;i++)
{
tx=list[head].x+dx[i];
ty=list[head].y+dy[i];
if (map[tx][ty]=='#') ans++;
else if (!bo[tx][ty])
{
tail++;
list[tail].x=tx;list[tail].y=ty;
bo[tx][ty]=true;
}
}
head++;
}
printf("%d\n",(ans-4)*9);//[1][1] 和[n][n] 两边多了四个，所以减去才行。
return 0;
}
【参考程序】：//floodfill(洪水算法)
#include<iostream>
using namespace std;
char map[40][40];
int a[40][40];
int n,ans;
void fill(int x,int y)
{
if (x<=0|x>n|y<=0|y>n) return ;
if (map[x][y]=='#') return ;
if (a[x][y]==0) return ;
a[x][y]=0;
fill(x-1,y);fill(x,y+1);
fill(x+1,y);fill(x,y-1);
}
int main()
{
scanf("%d",&n);getchar();
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
scanf("%c",&map[i][j]);
getchar();
}
memset(a,0xFF,sizeof(a));
fill(1,1);
fill(n,n);
ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (a[i][j]==0)
{
if (a[i-1][j]==-1) ans++;
if (a[i][j+1]==-1) ans++;
if (a[i+1][j]==-1) ans++;
if (a[i][j-1]==-1) ans++;
}
printf("%d\n",(ans-4)*9);
return 0;
}