글 읽기 - 저의 알고리즘이 틀린건가요 ? 읽어주세요 도움주세요 ㅠㅠ

blackpoplar1004 3년 전 0

토마토 문제와 같이 변화가 있을 때 계속 카운트 해주고

어차피 방문 한번하고 벽을 만났을 때 벽을 깰 수 없으니 push가 일어나지 않을 테니 .......

그러고 나서 최종까지 방문 못하면 -1을 출력하게 했습니다.

저의 알고리즘이 잘못되었을까요 ?

그리고 틀리는 이유를 아신다면 ... 알려주세요 ^^

#include<iostream>
#include <queue>
#include <tuple>
using namespace std; 

int dir[4][2] = { {1,0}, {-1,0} ,{0,1}, {0,-1} }; 
int map[1001][1001]; 
int visited[1001][1001]; 

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); 

	int n, m; 
	cin >> n >> m; 
	
	for (int y = 1; y <= n; y++)
	{
		string data; 
		cin >> data;
		for (int x = 0; x < data.size(); x++)
		{
			map[y][x+1] = data[x]-48;
		}
	}
	
	//=============================================
	bool chance = true; 
	queue<tuple<int,int,bool>> q;

	int cnt = 1; 
	int seg = 0; 
	int ans = 1; 
	// {1,1} == 1 일때
	if (map[1][1] == 1) {
		chance = false;
		q.push(make_tuple(1, 1, false));
	} 
	else
	{
		q.push(make_tuple(1, 1, true));
	}

	while (!q.empty())
	{
		seg = 0; 
		for (int i = 0; i < cnt; i++)
		{
			int x = get<1>(q.front());
			int y = get<0>(q.front());
			bool TF = get<2>(q.front());
			visited[y][x] = true; 
			q.pop();

			for (int d = 0; d < 4; d++)
			{
				int nX = x + dir[d][0];
				int nY = y + dir[d][1];
				
				if ((nX >= 1 && nX <= m) && (nY >= 1 && nY <= n) //범위 안에 있니 ? 
					&&(!visited[nY][nX])) //방문 안했고
				{
					if (!map[nY][nX])  // map은 0
					{
						q.push(make_tuple(nY, nX, TF));
						seg++;
						visited[nY][nX] = true;
					}
					else //map이 1 
					{
						if (TF) // 기회가 있으면
						{
							//TF = false;
							q.push(make_tuple(nY, nX, false)); 
							visited[nY][nX] = true;

							seg++;
						}
					
					}
				}
			}
		}
		cnt = seg; 
		if (seg) ans++; 
	}
	

	if (visited[n][m])
		cout << ans << "\n";
	else
		cout << -1 << "\n";
}

pichulia 3년 전 3

반례입니다.

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

문제

문제

출처

ICPC

저의 알고리즘이 틀린건가요 ? 읽어주세요 도움주세요 ㅠㅠ

blackpoplar1004 3년 전 0

pichulia 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말