백준 16973번 직사각형 탈출

문제

크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.

격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.

직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.

입력

첫째 줄에 격자판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 각 칸의 정보가 주어진다. 0은 빈 칸, 1은 벽이다.

마지막 줄에는 직사각형의 크기 H, W, 시작 좌표 Sr, Sc, 도착 좌표 Fr, Fc가 주어진다.

격자판의 좌표는 (r, c) 형태이고, r은 행, c는 열이다. 1 ≤ r ≤ N, 1 ≤ c ≤ M을 만족한다.

출력

첫째 줄에 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 1 ≤ H ≤ N
• 1 ≤ W ≤ M
• 1 ≤ Sr ≤ N-H+1
• 1 ≤ Sc ≤ M-W+1
• 1 ≤ Fr ≤ N-H+1
• 1 ≤ Fc ≤ M-W+1
• 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.

 

왼쪽 위로 visit처리하면 어차피 모양이 일치할 수 밖에 없음.

따라서 visit는 다른 좌표 신경쓸 필요 없고,

다만 유효성 체크를 잘 해줘야 하는데, 모든 좌표가 범위내에 있어야 하고, 벽이 있으면 안됨.

하지만 처음 직사각형의 영역에는 벽이 없다고 하였으므로 이동시에 경계에서 벽이 있는지 확인 하면됨.

따라서 for문 각 4개 위, 아래, 오른, 왼의 경계에 대해서 벽의 여부를 파악하면서 이동시켜주면 된다.

 

직사각형 내부 영역을 전부 탐색하면 시간초과임.

#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;

int N, M, H, W;
int arr[1001][1001];
bool visit[1001][1001];
int Sy, Sx, Fy, Fx;

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

struct Node
{
	int luy;
	int lux;
	int ruy;
	int rux;
	int ldy;
	int ldx;
	int rdy;
	int rdx;
	int cost;
};

bool check(Node node)
{
	if (node.luy >= 1 && node.luy <= N && node.ldy >= 1 && node.ldy <= N && node.ruy >= 1 && node.ruy <= N && node.rdy >= 1 && node.rdy <= N
		&& node.lux >= 1 && node.lux <= M && node.ldx >= 1 && node.ldx <= M && node.rux >= 1 && node.rux <= M && node.rdx >= 1 && node.rdx <= M)
	{
		for (int i = node.luy; i <= node.ldy; i++)
		{
			if (arr[i][node.lux])
			{
				return false;
			}
		}

		for (int i = node.ruy; i <= node.rdy; i++)
		{
			if (arr[i][node.rux])
			{
				return false;
			}
		}

		for (int i = node.lux; i <= node.rux; i++)
		{
			if (arr[node.luy][i])
			{
				return false;
			}
		}

		for (int i = node.ldx; i <= node.rdx; i++)
		{
			if (arr[node.ldy][i])
			{
				return false;
			}
		}
		return true;
	}
	return false;
}

int main(void)
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> arr[i][j];
		}
	}
	cin >> H >> W >> Sy >> Sx >> Fy >> Fx;

	queue<Node> que;
	que.push({ Sy, Sx , Sy , Sx + W - 1, Sy + H - 1, Sx , Sy + H - 1, Sx + W - 1, 0 });
	visit[Sy][Sx] = true;

	while (!que.empty())
	{
		Node dir = que.front();
		que.pop();

		if (dir.luy == Fy && dir.lux == Fx)
		{
			cout << dir.cost << endl;
			return 0;
		}

		for (int i = 0; i < 4; i++)
		{
			Node newDir = dir;
			newDir.ldy += dy[i];
			newDir.luy += dy[i];
			newDir.rdy += dy[i];
			newDir.ruy += dy[i];

			newDir.ldx += dx[i];
			newDir.lux += dx[i];
			newDir.rdx += dx[i];
			newDir.rux += dx[i];
			newDir.cost += 1;

			if (check(newDir))
			{
				if (!visit[newDir.ldy][newDir.ldx])
				{
					visit[newDir.ldy][newDir.ldx] = true;
					que.push(newDir);
				}
			}
		}

	}

	cout << -1 << endl;
}