글 읽기 - c++ 반례 구해봅니다.

cgc96 1년 전 0

틀린 이유는 알것같습니다.

visited[breaking][x][y]가 항상 최소 길이의 방문이 보장이 안되서 그런것 같습니다.

낮,밤의 영향으로 인해 같은 갯수의 벽을 뚫고, 더 적은 밤을 보내고, 적은 길이로 x,y로 도달 할 수 있는것인지 궁금합니다.

같은 갯수의 벽을 뚫었는데, 그 벽을 낮에 더 많이 뚫었다면 x,y에 먼저 도달해야 한다는 것이 제 생각입니다.

반례가 있다면 주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

char map[1001][1001];
bool visited[11][1001][1001];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int k, n, m;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> k;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> map[i][j];
		}
	}
	
	queue<tuple<int,int,int,int, bool>> q;
	q.push({0,0,0,1,false});
	
	int ans = 10000001;
	while(!q.empty()){
		int cx, cy, breaking, len, night;
		tie(cx, cy, breaking, len, night) = q.front();
		q.pop();
		
		if(cx == n-1 && cy == m-1){
			ans = min(ans, len);
			//cout << len << endl;
			continue;
		}
		
		for(int i = 0; i < 4; i++){
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			
			if(nx<0 || nx>=n || ny<0 || ny>=m)
				continue;
				
			if(map[nx][ny] == '0'){
				if(visited[breaking][nx][ny] == 0){
					visited[breaking][nx][ny] = 1;
					q.push({nx,ny,breaking,len+1,!night});
				}
			}
			else{
				if(breaking < k && visited[breaking+1][nx][ny] == 0){
					
					if(night == true){
						q.push({cx,cy,breaking,len+1,!night});
					}else{
						q.push({nx,ny,breaking+1,len+1,!night});
						visited[breaking+1][nx][ny] = 1;
					}

				}
			}
		}
	}
	if(ans == 1000001)
		cout << -1;
	else
		cout << ans;
	return 0;
}

yuris 1년 전 1

반례입니다. 불가능 할 때 처리를 다시 한번 확인해보세요.

INPUT:
3 3 2
0 1 1
1 1 1
1 1 0

ANS:
-1

OUTPUT:
10000001

cgc96 1년 전 0

헉 알고리즘에는 문제가 없었군요...
감사합니다.

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

문제

문제

출처

ICPC

c++ 반례 구해봅니다.

cgc96 1년 전 0

yuris 1년 전 1

cgc96 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말