AOJ.869 미로


Time Limit: 1000 ms   Memory Limit: 50 MB
Total Submission: 21   Submission Accepted: 11
Judge By Case
Description
미궁의 관리자 들 은 새로운 시작 계절 에 새로운 벽 지 를 사용 하기 로 했다.이 목적 에서 그들 은 절차 가 필요 하 다.
미궁 내 벽의 면적 을 계산 합 니 다.이것 이 바로 네가 곧 해 야 할 일이 다.
우 리 는 이 미 로 를 N*N(3<=N<=33)의 행렬 로 표시 한다.일부 행렬 단원 은"."를 포함한다.
(이것 은 빈 사각형 을 대표 합 니 다)다른 행렬 단원 은'\#'을 포함 합 니 다.(이것 은 큰 돌 로 쌓 은 돌담 을 대표 합 니 다.
차지 한 사각형.모든 사각형 의 크기 는 3*3 평방미터 이다.
벽 은 미로 의 사방(미로 의 출입구 로 서 의 왼쪽 상단 과 오른쪽 하단 을 제외 하고)과 그 표 시 된 것 이다.
'\#'의 행렬 단원 구성 은 그 외 에 다른 벽 이 없다.입력 한 행렬 에서 왼쪽 상단 과 오른쪽 하단 은 영원히
하나너의 임 무 는 미로 에서 볼 수 있 는 부분의 벽의 면적 을 계산 하 는 것 이다.다시 말 하면 미로 에 대한 여행 이다.
손님 은 벽 표면 에 보 이 는 부분 을 말한다.두 개의 돌 이 모퉁이 에 있어 도 인접 한 돌 사이 에 틈 이 없 도록 주의해 라.
서로 접촉 하면 우 리 는 모두 그것들 이 인접 한 것 이 라 고 생각한다.그림 의 예 를 들 어 미로 에서 볼 수 있 는 벽 은 모두 굵 은 선 으로 한다.
묘사 하 다.모든 벽의 높이 는 3 미터 이다.
Input
입력 한 첫 줄 에는 숫자 N 이 포함 되 어 있 습 니 다.다음 N 줄 에는 줄 마다 N 글자 가 포함 되 어 있 습 니 다.줄 마다 미 로 를 묘사 했다.
행렬 의 한 줄.줄 마다'...','\#'두 글자 만 있 고 줄 바 꿈 문자 로 끝 납 니 다.입력 에 없 음
어떠한 빈 칸 도
Output
프로그램 은 필요 한 벽지 의 정확 한 면적 인 정 수 를 출력 해 야 합 니 다.
Sample Input
Original
Transformed

5
.....
...##
..#..
..###
.....

5[EOL] 
.....[EOL] 
...##[EOL] 
..#..[EOL] 
..###[EOL] 
.....[EOF] 

Sample Output
Original
Transformed

198

 
   
             ，     dfs
  
 
   
#include
#include
#include
#include
#include
#include
//#define DEBUG
const int maxn =50;
using namespace std;
int G[maxn][maxn];
int  n, ans;
int dir[][2] = { {1,0},{0,1},{-1,0},{0,-1} };
char s[maxn];
void dfs(int x, int y);
bool check(int x, int y);
int main() {
#ifdef DEBUG
	freopen("Text.txt", "r", stdin);
#endif // DEBUG
	
	while (scanf("%d",&n)!=EOF) {
		memset(G, 0, sizeof(G));
		ans = 0;
		int i, j;
		for (i = 1; i <= n; i++) {
			scanf("%s", s + 1);
			for (j = 1; j <= n; j++) {
				if (s[j] == '.')
					G[i][j] = 1;
			}
		}
		/*for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++) {
				cout << G[i][j];
			}
			cout << endl;
		}*/
		dfs(1, 1);
		dfs(n, n);
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++) {
				if (G[i][j] == 2) {
					for (int k = 0; k < 4; k++) {
						int xx = i + dir[k][0];
						int yy = j + dir[k][1];
						if (G[xx][yy]==0)
							ans++;
					}
				}
			}
		}
		printf("%d
", (ans-4)*9);
	}
	
	
	return 0;
}
void dfs(int x, int y) {
	
	if (!check(x, y))
		return;
	printf("x = %d  y = %d
", x, y);
	G[x][y] = 2;
	dfs(x - 1, y);
	dfs(x + 1, y);
	dfs(x, y - 1);
	dfs(x, y + 1);
}
bool check(int x, int y) {
	if (x > 0 && x <= n&&y > 0 && y <= n&&G[x][y]==1)
		return true;
	return false;
}