URAL/1033

来自"NOCOW"

BFS，把碰到的墙都累加起来即可。注意可能st与ed不连通，那时候就要从ed也BFS一次，累加墙。

const maxn=33;
var n : integer;
    ans : longint;
    f : array[1..maxn,1..maxn] of char;
    a : array[0..maxn+1,0..maxn+1] of integer;
    i,j : integer;
procedure floodfill(x,y : integer);
begin
  if (x>n) or (y>n) or (x=0) or (y=0) then exit;
  if a[x,y]=0 then exit;
  if f[x,y]='#' then exit;
  a[x,y]:=0;
  floodfill(x+1,y); floodfill(x-1,y);
  floodfill(x,y+1); floodfill(x,y-1);
end;
begin
  readln(n); ans:=0;
  fillchar(a,sizeof(a),255);
  for i := 1 to n do
    begin
      for j := 1 to n do
        read(f[i,j]);
      readln;
    end;
  floodfill(1,1); floodfill(n,n);
  for i := 1 to n do
    begin
      for j := 1 to n do
        if a[i,j]=0 then begin
                           if a[i-1,j]=-1 then inc(ans);
                           if a[i,j-1]=-1 then inc(ans);
                           if a[i,j+1]=-1 then inc(ans);
                           if a[i+1,j]=-1 then inc(ans);
                         end;
    end;
  dec(ans,4); writeln(ans*3*3);
end.                                   [By Eugene.X]

//（来自田田，痴心C++）http://www.cppblog.com/tianlearn-language/
//我用的是DFS，上面说过了，就不解释了，两个入口都要搜。
//下面的代码原正方形四周都加了强，即都赋值为'#'(除了两个入口那)这样在处理四边时就不需要特殊的处理
#include<iostream>
#include<cstring>
using namespace std;
 
int const maxSize=35;
 
class ural1033
{
public:
    ural1033(){ size=0; memset(f,0,sizeof f); }
    void input();
    void search(int i, int j);
    int size;
    int getn(){return N;}
private:
    char a[maxSize][maxSize];
    bool f[maxSize][maxSize];
    int N;
};
 
void ural1033::input()
{
     cin>>N;
     int i,j;
     for(i=1; i<=N; i++)
        for(j=1; j<=N; j++)
            cin>>a[i][j];
    for(i=2; i<=N+1; i++)a[0][i]='#';
    for(i=2; i<=N+1; i++)a[i][0]='#';
    for(i=1; i<=N-1; i++)a[N+1][i]='#';
    for(i=1; i<=N-1; i++)a[i][N+1]='#';
 
}
 
void ural1033:: search(int i, int j)
{
    if(i<1||i>N||j<1||j>N||a[i][j]=='#'||f[i][j]==1)return ;
    f[i][j]=1;
    if(a[i-1][j]=='#')size++;
       else search(i-1,j);
    if(a[i][j-1]=='#')size++;
       else search(i,j-1);
    if(a[i][j+1]=='#')size++;
       else search(i,j+1);
    if(a[i+1][j]=='#')size++;
       else search(i+1,j);
}
 
 
int main()
{
    ural1033 ural;
    ural.input();
 
    ural.search(1,1);
    ural.search(ural.getn(),ural.getn());
 
    cout<<ural.size*9<<endl;
 
    system("pause");
    return 0;
}