[BOJ] 3495 - 아스키 도형 풀이

1. 문제

문제

창영이는 메모장에 '.', '\', '/'을 이용해서 도형을 그렸다. 각 문자는 그림에서 1*1크기의 단위 정사각형을 나타낸다.

'.'은 빈 칸을 나타내며, '/'는 정사각형의 왼쪽 아래 꼭지점과 오른쪽 위 꼭지점이 연결된 선분을, '\'은 왼쪽 위 꼭지점과 오른쪽 아래 꼭지점이 연결된 선분을 나타낸다.

창영이가 그린 도형의 넓이를 출력하는 프로그램을 작성하시오.

입력

 

첫째 줄에 h와 w가 주어진다. h는 그림의 높이, w는 너비이다. (2 ≤ h,w ≤ 100)

다음 h개 줄에는 창영이가 메모장에 그린 다각형이 주어진다.

창영이가 그린 다각형은 1개이고, 변과 변이 서로 교차하는 경우는 없고, 자기 자신과 접하는 경우도 없다.

출력

 

첫째 줄에 다각형의 넓이를 출력한다.

예제 입력

4 4

/\/\

\../

.\.\

..\/

예제 출력

8

힌트

 

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

 

 

2. 해답

 이 문제는 알고리즘이 아닌 문제해결능력을 필요로 하는 문제이다.

주 포인트는 다각형의 넓이를 계산할 때 \, /의 경우 위쪽 혹은 아래쪽 삼각형을 포함하고 있으므로 1/2을 무조건 가져간다. 반면 .의 경우에는 다각형 안에 포함되어 있을 수도있고 아닐 수도 있다. 이 칸이 다각형안에 포함되어 있는지 여부는 \와 /의 개수로 알 수 있다. 만약 다각형 안에 포함된 사각형이라면 반드시 \ 또는 / 다음에 있을 것이다. 즉, 홀수번째 \ 또는 / 다음에 나오는 .은 포함되는 것이고 짝수번째에 나오는 .은 포함되지 않는다.

 1) \와 /칸은 무조건 1/2

2) \,/의 홀수번째 다음에 나타나는 .은 1, 짝수번째 나오는 .은 0

#include <bits/stdc++.h>
#define pb(a) push_back(a)
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair((a),(b))
#define ff first
#define ss second

using namespace std;

typedef long long lld;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int INF = 987654321;
const long long LINF = 9876543212345;

int W,H;
char board[102][102];
bool in[102][102];
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
#endif
	scanf("%d%d",&H,&W);
	int i,j,k;
	for(i=1;i<=H;++i)scanf("%s",board[i]+1);
	for(i=1;i<=H;++i){
		bool out = true;
		for(j=1;j<=W;++j){
			if(board[i][j]=='/' || board[i][j]=='\\'){
				out ^= 1;
				in[i][j] = 1;
			}else if(!out)in[i][j] = 1;
		}
	}
	int sum = 0;
	int cnt = 0;
	for(i=1;i<=H;++i)for(j=1;j<=W;++j){
		if(board[i][j]=='/' || board[i][j]=='\\')++cnt;
		else if(in[i][j])++sum;
	}
	printf("%d\n",sum + (cnt>>1));	
#ifndef ONLINE_JUDGE
	fclose(stdin);
#endif
}