Educational Codeforces Round 88 (Rated for Div. 2) B - New Theatre Square 풀이

Educational Codeforces Round 88 (Rated for Div. 2) B - New Theatre Square 코드포스 풀이

 

https://codeforces.com/contest/1359/problem/B

Problem - B - Codeforces

 

어? BFS? DFS?.. B번 문제에 벌써 나온다고???

 

"SAME ROW"

대회 종료 후에 소스를 엎고 5분만에 해결했다.

---

< 문제 설명 >

테스트케이스 t가 주어지고, n개의 열, m개의 행, 빈 칸 하나의 값인 x, 빈 칸 두개의 값인 y가 주어진다.

.

.

.

위 두가지 경우처럼 . 으로만 찍힌 칸만 계산이 가능하며

*

별이 찍힌 칸은 계산할 수 없다.(무시한다)

---

< 예제 >

3 3 3 7

.	.	*
*	.	.
.	*	.

 

. 하나는 3

.이 가로로 2개 있으면(..) 7의 값을 가진다.

 

이 때의 최소가 되는 값을 구하시오.

 

우선, x와 y중 더 작은 값을 찾아야 한다.

 

.

.

 

두 칸이 있을 때, X의 값과 Y의 값중 무엇으로 계산할 것인가?

즉, 2*X 와 Y 중 어떤 값이 더 작은가?

 

해당 예제의 경우 2X의 값이 더 작으므로 모든 . 칸의 갯수만 파악하고 X의 값을 더해버리면 쉽게 끝난다.

 

반대의 경우(2*X보다 Y가 더 작은 경우), 두 칸씩 있는 것을 먼저 계산하고 한 칸만 남겨지는 경우엔 X를 더해주면 된다.

 

---

import sys
input = sys.stdin.readline
t=int(input().strip())

while t:
    ans=0
    t-=1
    n,m,x,y=map(int,input().split())
    field=list('.'*m for _ in range(n))
    
    for i in range(n):
        field[i]=list(input().strip())

    if 2*x<=y:
        for i in range(n):
            for j in range(m):
                if field[i][j]=='.':
                    ans+=x
    else:
        for i in range(n):
            j=0
            while j+1<=m:
                if field[i][j:j+2]==['.','.']:
                    j+=1
                    ans+=y
                elif field[i][j]=='.':
                    ans+=x
                j+=1
    print(ans)