백준 16973번 직사각형 탈출

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

16973번: 직사각형 탈출

 

 

 

 

 

<접근방법>

사이즈가 있는 직사각형의 bfs입니다.

큐에 넣을때마다 2중 for문으로 확인 작업을 하면 시간초과가 납니다.

 

bfs를 돌리기 전에 좌측상단의 점을 기준으로 잡고 그 점이 가지못하는 곳에 방문체크를 했습니다.

이렇게 하면 일반 bfs와 똑같아집니다.

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

const int MAX = 1000;
int n, m, h, w, sy, sx, fy, fx;
int map[MAX][MAX];
bool visit[MAX][MAX];
int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

struct point {
	int y, x, cnt;
};

queue<point> q;

bool check(int y, int x) {
	for (int ty = y; ty < y + h; ty++) {
		for (int tx = x; tx < x + w; tx++) {
			if (ty < 0 || ty >= n || tx < 0 || tx >= m) return false;
			if (map[ty][tx] == 1) return false;
		}
	}

	return true;
}

int bfs() {
	q.push({sy, sx, 0});
	visit[sy][sx] = true;
	
	while (!q.empty()) {
		point t = q.front();
		q.pop();

		if (t.y == fy && t.x == fx) return t.cnt;

		for (int i = 0; i < 4; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];

			if (ty < 0 || ty + h-1 >= n || tx < 0 || tx + w-1 >= m) continue;
			if (visit[ty][tx]) continue;
			
			q.push({ty, tx, t.cnt + 1});
			visit[ty][tx] = true;
		}
	}
	return -1;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	cin >> h >> w >> sy >> sx >> fy >> fx;
	sy--; sx--; fy--; fx--;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1) {
				for (int y = i; y > i - h; y--) {
					if (y < 0) break;
					for (int x = j; x > j - w; x--) {
						if (x < 0) break;
						visit[y][x] = true;
					}
				}
			}
		}
	}

	/*puts("");
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << visit[i][j] << ' ';
		}
		puts("");
	}*/

	cout << bfs() << '\n';

	return 0;
}