티스토리 뷰

 

BFS를 돌려서 푸는 문제다

성을 넣지말고 반대로 모래를 넣으면 쉽게 풀 수 있다

 

모래를 기준으로 8방향을 보면서 성이 있다면 1씩 감소시켜준다

만약 성의 견고함이 0이 된다면 모래로 바꾸고 큐에 넣어주면 된다

 

풀긴 풀었는데 시간이 좀 너무 오래걸렸다.. 왜지..!

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int arr[1010][1010];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
int n,m;
 
bool inner(int x,int y){
    return (0<=&& x<&& 0<=&& y<m);
}
int main(){
    int t; scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        scanf(" %d %d",&n,&m);
 
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                char c; scanf(" %1c",&c);
                if('1'<=c&&c<='9') arr[i][j]=c-'0';
            }
        }
        
        queue<pair<int,int>> q;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]) continue;
                q.push({i,j});
            }
        }
        
        int ans=0;
        while(int s = q.size()){
            while(s--){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
 
                for(int i=0;i<8;i++){
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    if(inner(nx,ny) && arr[nx][ny]){
                        arr[nx][ny]--;
                        if(!arr[nx][ny]) q.push({nx,ny});
                    }
                }
            }
            ans++;
        }
        printf("#%d %d\n",tc,ans-1);
    }
}
 
 

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

[SWEA] 7988 내전 경기  (0) 2020.03.04
[SWEA] 8275 햄스터  (0) 2020.03.04
[SWEA] 8382 방향전환  (0) 2020.03.03
[SWEA] 4534 트리 흑백 색칠  (0) 2020.03.02
[SWEA] 1247 최적경로  (0) 2020.02.19
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함