[BOJ/백준][Gold4] 16973 : 직사각형 탈출 (C++)

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

16973번: 직사각형 탈출

 

 

[난이도] Gold4
[유형] BFS

[풀이]
왼쪽 끝점을 기준으로 BFS를 돌려줍니다.
직사각형을 옮길 수 있을지 판단할 때, 세로H, 가로W의 모든 점을 검사하면 시간초과가 발생하게 되므로
누적합 배열을 미리 만들어 놓은 뒤, 옮길 위치의 사각형에 1(벽)이 포함되어 있는지를 O(1)에 판별하도록 해줍니다.

 

#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,board[1001][1001],H,W,sy,sx,ey,ex,sum[1001][1001];
bool visit[1001][1001];
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
bool check(int y,int x){
    if(y<1||x<1||y>N||x>M||y+H-1<1||x+W-1<1||y+H-1>N||x+W-1>M) return 0;
    if(sum[y+H-1][x+W-1]-sum[y-1][x+W-1]-sum[y+H-1][x-1]+sum[y-1][x-1]>0) return 0;
    return 1;
}
int bfs(){
    queue<pair<int,int>> q;
    q.push({sy,sx});
    visit[sy][sx]=1;
    int ret=0;
    while(!q.empty()){
        int sz= q.size();
        while(sz--){
            auto [y,x] =q.front(); q.pop();
            if(y==ey&&x==ex) return ret;
            for(int i=0;i<4;i++){
                int ny=y+dy[i];
                int nx=x+dx[i];
                if(!check(ny,nx) || visit[ny][nx]) continue;
                q.push({ny,nx});
                visit[ny][nx]=1;
            }
        }
        ret++;
    }
    return -1;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++) {
            scanf("%d",&board[i][j]);
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+board[i][j];
        }

    scanf("%d%d%d%d%d%d",&H,&W,&sy,&sx,&ey,&ex);
    printf("%d",bfs());
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16973.cpp