글 읽기 - bfs visit 배열 크기 문제.. ㅠㅠ도와주세용....

jangzzang 4년 전 0

간략히 적어보자면 문제는 벽이 아닌 곳을 상하로는 제한없이 이동할 수 있고, 좌 우로는 좌측제한 L 우측이동제한 R 이 입력됩니다.

그래서, q상태에 좌표 x,y와 좌측으로 갈 수 있는 회수 L, 우측으로 갈 수 있는 회수 R을 넣어 주면서 bfs를 돌렸습니다. 93퍼쯤에서 틀렸습니다가 나오네

요 ㅠㅠ

생각 해 보니까 좌표뿐만아니라 그 좌표에 도달했을떄, L,R도 방문 체크를 함께 해야하는 것 같은데,, 4차원 vtd[1000][1000][1000][1000]은 말도 안되

고 어떤 방법으로 방문 체크를 해야할까요 ..

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef struct {
	int x;
	int y;
	int left;
	int right;
}INFO;
int n, m, L, R;
int map[1005][1005];
bool vtd[1005][1005];
int mx[4] = { -1,0,1,0 };
int my[4] = { 0,1,0,-1 };
int sx, sy, ans;
queue<INFO> q;
void bfs();
bool isInside(int x,int y);
int main() {
	scanf("%d %d", &n, &m);
	scanf("%d %d", &L, &R);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &map[i][j]);
			if (map[i][j] == 2) {
				sx = i;
				sy = j;
				map[i][j] = 0;
			}
		}
	}
	bfs();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (vtd[i][j]) {
				ans++;
			}
		}
	}
	printf("%d", ans);
}
void bfs() {
	vtd[sx][sy] = true;
	q.push({ sx,sy,L,R });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int l = q.front().left;
		int r = q.front().right;
		q.pop();
		//위로 가고
		int tx = x + mx[0];
		int ty = y + my[0];
		if (isInside(tx,ty) && map[tx][ty] == 0 && !vtd[tx][ty]) {
			vtd[tx][ty] = true;
			q.push({ tx,ty,l,r });
		}
		//아래로 가고 
		tx = x + mx[2];
		ty = y + my[2];
		if (isInside(tx, ty) && map[tx][ty] == 0 && !vtd[tx][ty]) {
			vtd[tx][ty] = true;
			q.push({ tx,ty,l,r });
		}
        //좌측
		tx = x + mx[3];
		ty = y + my[3];
		if (isInside(tx, ty) && !vtd[tx][ty] && map[tx][ty] == 0 && l >= 1) {
			q.push({ tx,ty,l - 1,r });
			vtd[tx][ty] = true;
		}
        //우측
		tx = x + mx[1];
		ty = y + my[1];
		if (isInside(tx, ty) && !vtd[tx][ty] && map[tx][ty] == 0 && r >= 1) {
			q.push({ tx,ty,l,r - 1 });
			vtd[tx][ty] = true;
		}	
	}
}

bool isInside(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= m)return true;
	return false;
}

nahwasa 4년 전 1

일단 네 4차원은 필요없구요..

일단은 위아래로 한칸씩 이동하셨기 때문이네요!

https://www.acmicpc.net/board/view/37868

jangzzang 4년 전 1

감사합니다 덕분에 해결했습니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

bfs visit 배열 크기 문제.. ㅠㅠ도와주세용....

jangzzang 4년 전 0

nahwasa 4년 전 1

jangzzang 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말