2016년 4월 5일 화요일

9518 - 로마 카톨릭 미사

https://www.acmicpc.net/problem/9518

다른 사람 소스를 보니까 내가 너무 어렵게 생각했던 것 같다.

(i, j)에서 주변 각 8방향에 대해 악수를 했다/안했다로 xxxxxxxx의 비트로 저장해서 주변 8방향을 하나씩 악수했다. (비트를 참고하여 이미 악수했다면 횟수로 세지 않았다.)


#include <cstdio>
#include <cstring>

int DY[]={-1,-1,-1,0,0,1,1,1};
int DX[]={-1,0,1,-1,1,-1,0,1};

int main(){
    int i, j, h, w;
    scanf("%d %d ", &h, &w);
    char s[50][51];
    for(i=0; i<h; ++i) scanf("%s ", s[i]);
    
    int y=0, x=0, shakeCount=0;
    for(i=0; i<h; ++i){
        for(j=0; j<w; ++j){
            if(s[i][j] != '.') continue;
            int r = 0;
            for(int k=0; k<8; ++k){
                int dy=i+DY[k], dx=j+DX[k];
                if(dy < 0 || dy >= h || dx < 0 || dx >= w) continue;
                r += s[dy][dx] == 'o';
            }
            if(shakeCount < r){
                shakeCount = r, y = i, x = j;
            }
        }
    }
    s[y][x] = 'o';
    int r = 0;
    int shake[50][50]={};
    for(i=0; i<h; ++i){
        for(j=0; j<w; ++j){
            if(s[i][j] != 'o') continue;
            for(int k=0; k<8; ++k){
                int dy=i+DY[k], dx=j+DX[k];
                if(dy < 0 || dy >= h || dx < 0 || dx >= w || s[dy][dx] != 'o') continue;
                int bit = 1<<(7-k);
                r += (shake[dy][dx] & bit) == bit;
                shake[i][j] |= 1<<k;
                shake[dy][dx] |= bit;
            }
        }
    }
    printf("%d", r);
    return 0;
}
댓글 쓰기

게시글 목록