글 읽기 - 게시판의 예시 입출력도 다 맞고, 틀릴게 없는거 같은데 계속 오답으로 나오네요.

applepie77 4년 전 1

추가로 놓는 오작교는 맵에서 0인 지점에 1개만,

가로 세로 교차점 절벽은 오작교 못 건설,

오작교를 건넌 다음은 무조건 맵에서 1인 지점으로 이동.

위 조건을 모두 만족시키고, 게시판 테케도 전부 맞는데,

뭐를 빠트린건지 모르겠네요.

#include <iostream>
#include <queue>

using namespace std;

int N, T;

queue<pair<int, int>>q_1; // <<y, x>
queue<pair<int, int>>q_2; // <현재시간, 오작교건설>>

int map_[11][11] = {0};
int depth_map[11][11];

int y_mv[5] = {0, 1, -1, 0, 0};
int x_mv[5] = {0, 0, 0, -1, 1};

int check_y[4] = {1, -1, 1, -1};
int check_x[4] = {-1, -1, 1, 1};

int flag_ = 0;

void my_bfs(){
	int next_y, y_;
	int next_x, x_;
	int build_;
	int time_now, time_left; 
	
	while(!q_1.empty()){
		y_ = q_1.front().first;
		x_ = q_1.front().second;
		time_now = q_2.front().first;
		build_ = q_2.front().second;
		q_1.pop();
		q_2.pop();
		for(int i = 1; i < 5; i++){
			next_y = y_ + y_mv[i];
			next_x = x_ + x_mv[i];
			if(next_y < 0 || next_x < 0 || next_y >= N || next_x >= N){ continue; }
			
			if(map_[next_y][next_x] == 1){
				
				if(time_now + 1 <= depth_map[next_y][next_x]){
					
					depth_map[next_y][next_x] = time_now + 1;
					q_1.push(make_pair(next_y, next_x));
					q_2.push(make_pair(time_now + 1, build_));
					
				}
				
			}
			else if(map_[y_][x_] == 1 && map_[next_y][next_x] != 1){
				
				if(map_[next_y][next_x] == 0 ){
					flag_ = 0;
					
					for(int j = 0; j < 4; j++){
						
						int chk_y_1 = next_y + check_y[j];
						int chk_x_1 = next_x;
						int chk_y_2 = next_y;
						int chk_x_2 = next_x + check_x[j];
						
						if(chk_y_1 < 0 || chk_x_2 < 0 || chk_y_1 >= N || chk_x_2 >= N){ continue; }
						if((map_[chk_y_1][chk_x_1] == 0 || map_[chk_y_1][chk_x_1] >= 2) && ((map_[chk_y_2][chk_x_2] == 0) ||(map_[chk_y_2][chk_x_2] >= 2)) ){
							flag_ = 1;
						}
						
					}
					
					
					if(build_ == 1 || flag_ == 1){ continue; }
					
					time_left = T - (time_now % T);
					
					if(time_now + time_left <= depth_map[next_y][next_x]){
						depth_map[next_y][next_x] = time_now + time_left;
						q_1.push(make_pair(next_y, next_x));
						q_2.push(make_pair(time_now + time_left, 1));
					}
				}
				else{
					
					time_left = map_[next_y][next_x] - (time_now % map_[next_y][next_x]);
					
					if(time_now + time_left <= depth_map[next_y][next_x]){
						depth_map[next_y][next_x] = time_now + time_left;
						q_1.push(make_pair(next_y, next_x));
						q_2.push(make_pair(time_now + time_left, build_));
					}
					
				}
				
				
			}
		}
	}
	
}

int main(){
	
	cin.tie(0);
	
	scanf("%d %d", &N, &T);
	for(int y = 0; y < N; y++){
		for(int x = 0; x < N; x++){
			cin >> map_[y][x];
			depth_map[y][x] = 999999999;
		}
	}
	
	q_1.push(make_pair(0, 0));
	q_2.push(make_pair(0, 0));

	my_bfs();
	
	cout << depth_map[N-1][N-1];

	return 0;
}

rumble99 4년 전 1

8 2
1 1 1 1 0 1 1 1
1 1 0 1 0 1 0 1
0 0 0 1 1 1 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 10
0 0 0 0 0 0 1 1

Answer : 20

Output: 21

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

문제

문제

출처

ICPC

게시판의 예시 입출력도 다 맞고, 틀릴게 없는거 같은데 계속 오답으로 나오네요.

applepie77 4년 전 1

rumble99 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말