poj 4022 ASCII Area dfs求二維面積
題意：
給一個有'/','\','.'組成的二維字符數組，求圖中‘/’和‘\’組成的面積有多大。
分析：
每個‘/’和‘\’的格每個貢獻1/2的面積，每個多邊形內部的'.'貢獻1的面積，關鍵是求多邊形內部的’.‘有多少個。一開始往上下左右4個方向搜wa了，原來內部的點可以斜著擴展，比如/./這種情況。但斜著搜要注意避免從多邊形內部跑到外部的情況，比如題目中給的sample。
代碼：
//poj 4022
//sep9
#include
using namespace std;
const int maxN=128;
int h,w,ans;
char g[maxN][maxN];
int vis[maxN][maxN];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int ddx[4]={-1,1,1,-1};
int ddy[4]={1,-1,1,-1};
int dfs(int i,int j)
{
vis[i][j]=1;
int s=1;
for(int k=0;k<4;++k){
int nx=i+dx[k];
int ny=j+dy[k];
if(nx<0||nx>=h||ny<0||ny>=w)
return -1;
if(g[nx][ny]=='.'&&vis[nx][ny]==-1){
int t=dfs(nx,ny);
if(t==-1)
return -1;
s+=t;
}
}
for(int k=0;k<4;++k){
int nx=i+ddx[k];
int ny=j+ddy[k];
if(nx<0||nx>=h||ny<0||ny>=w)
return -1;
int minx=min(nx,i);
int miny=min(ny,j);
int maxx=max(nx,i);
int maxy=max(ny,j);
if((minx==nx&&miny==ny)||(minx==i&&miny==j))
if(g[minx][miny+1]=='/')
continue;
if((minx==nx&&maxy==ny)||(minx==i&&maxy==j))
if(g[minx][miny]=='\\')
continue;
if(g[nx][ny]=='.'&&vis[nx][ny]==-1){
int t=dfs(nx,ny);
if(t==-1)
return -1;
s+=t;
}
}
return s;
}
int main()
{
scanf("%d%d",&h,&w);
for(int i=0;i
