기로에 서다

문제 www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 1. 간단하게 생각해본다면 시작 점에서부터 BFS를 돌려 "왼쪽 위 점에서부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 확인하며 진행하면 될 것 같지만 $O(n*m*h*w)$로 시간 초과가 납니다. 2. "해당 점에서 부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 연산하며 중복된 칸을 계속 탐색하므로 이를 막기 위해 dp를 사용합니다. 이때 상태 정의는 "dp[i]..