程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 4022 ASCII Area dfs求二維面積

poj 4022 ASCII Area dfs求二維面積

編輯:C++入門知識

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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved