글 읽기 - 3시간 동안 고민 중이에요 왜 안되는지 알려주세요ㅜㅜ

blackpoplar1004 2년 전 0

3차원 배열로 하지 않았습니다.

temp에서 뚫었는지 안 뚫었는지 유무를 저장해서 마지막까지 들고 가니 문제 없는거 같은데

무슨 이유로 안되는건가요 ?

#include <iostream> 
#include <vector>
#include <queue>
#include<cstring>
#include <algorithm>
using namespace std;

#define MAX 1000

using IIT = pair<int, int>;
bool visit[MAX][MAX];
int wall[MAX][MAX]; 

int gWide, gHigh;

int gMoveX[4] = { 0, 0, -1,  1}; // 상 하 좌 우 
int gMoveY[4] = {-1, 1 , 0 , 0};

void bfs(IIT _Data)
{
	queue<pair<IIT, IIT>> que;
	que.push(make_pair(make_pair(_Data.first, _Data.second), make_pair(1, 0)));
	visit[_Data.first][_Data.second] = true;

	while (!que.empty())
	{
		pair<IIT, IIT> temp = que.front();
		int x = temp.first.first;
		int y = temp.first.second;

		if (x == gWide - 1 && y == gHigh - 1)
		{
			cout << temp.second.first << endl;
			return;
		}
		que.pop();

		for (int i = 0; i < 4; ++i)
		{
			int posx = x + gMoveX[i];
			int posy = y + gMoveY[i];
			int breakCnt = temp.second.second; 
			if (posx >= 0 && posx < gWide && posy >= 0 && posy < gHigh)
			{
				if (!wall[posy][posx])
				{
					if (!visit[posy][posx])
					{
						visit[posy][posx] = true;
						que.push(make_pair(make_pair(posx, posy),
							make_pair(temp.second.first + 1, breakCnt)));
					}
				}
				else if (wall[posy][posx] && !breakCnt)
				{
					if (!visit[posy][posx])
					{
						visit[posy][posx] = true;
						que.push(make_pair(make_pair(posx, posy),
							make_pair(temp.second.first + 1, breakCnt + 1)));
					}
				}
			}
		}
	}

	cout << -1 << endl;
	return;
}

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie();
	std::cout.tie();

	// ===================================
	cin >> gHigh >> gWide;

	
	memset(visit, false, sizeof(visit));
	memset(wall, 0, sizeof(wall));

	for (int w = 0; w < gHigh; ++w)
	{
		for (int h = 0; h < gWide; ++h)
		{
			char Iswall;
			cin >> Iswall ;
			wall[w][h] = Iswall - '0';
		}
	}
	
	bfs(make_pair(0, 0)); 
}

djm03178 2년 전 0

단순히 큐에 벽을 뚫었는지 여부를 넣는 것만으로 되지 않기 때문에, 바로 그 이유로 3차원 배열을 쓰는 것입니다.

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

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

문제

문제

출처

ICPC

3시간 동안 고민 중이에요 왜 안되는지 알려주세요ㅜㅜ

blackpoplar1004 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말