글 읽기 - 제발!! 도대체 뭐가 틀린 거죠???

ekdlemdjq456 3년 전 0

제발!! 도대체 뭐가 틀린 거죠??? 질문 검색에서 올라와있는 반례들은 모두 검토해봤고 아무리 봐도 틀린 게 없는 것 같은데...

제출하자 마자 바로 틀립니다...

제가 뭘 잘 못 했을까요...??

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <cstring>

using namespace std;

int N, M, N_oil;
int input_map[20][20];
int to_x[4] = { 1, -1, 0, 0 };
int to_y[4] = { 0, 0, -1, 1 };
int taxi_x, taxi_y;
int visit_bfs[20][20];
bool possible=true;



class PASS {
public:
	bool ride;        // 이미 태운 승객
	int cur_x, cur_y; // 출발
	int dst_x, dst_y; // 목적지
	int min_distance; // 승객들의 출발지에서 목적지까지의 거리
};
PASS passanger[401];

queue<pair<int, pair<int, int>>> q_bfs;


int min_distance(int cur_y, int cur_x, int dst_y, int dst_x) { // 출발지에서 도착지 거리 구하기
	for(int i=0; i<N; i++)
	    for(int j=0; j<N; j++)
	        visit_bfs[i][j]=0;
	
	int distance = 0;
	int pop_y = cur_y, pop_x = cur_x;
	int push_y, push_x;
	q_bfs.push(make_pair(distance, make_pair(cur_y, cur_x)));
	while (pop_y != dst_y || pop_x != dst_x) {
	    if(q_bfs.empty())   // 도착지로 가지 못 하는 경우
	        return -1;
		pop_y = q_bfs.front().second.first;
		pop_x = q_bfs.front().second.second;
		distance = q_bfs.front().first;
		q_bfs.pop();
		for (int i = 0; i < 4; i++) {
			push_y = pop_y + to_y[i];
			push_x = pop_x + to_x[i];
			
			if (push_y < 0 || push_y >= N || push_x < 0 || push_x >= N)
				continue;
			if (visit_bfs[push_y][push_x] != 0 || input_map[push_y][push_x] != 0)
				continue;
			if (push_y == dst_y && push_x == dst_x) { //도착지에 도착한 경우
				while (!q_bfs.empty())
					q_bfs.pop();
				return (distance + 1);
				
			}	
			if (input_map[push_y][push_x] == 0) {
				q_bfs.push(make_pair(distance+1, make_pair(push_y, push_x)));
				visit_bfs[push_y][push_x] = distance;
			}
		}
	}
	return distance; // 출발하자 마자 바로 도착하는 경우
}

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> N_oil;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> input_map[i][j];

	cin >> taxi_y >> taxi_x;
	taxi_y--, taxi_x--;
	int t_cur_y, t_cur_x, t_dst_y, t_dst_x;
	for (int i = 1; i <= M; i++) {
		passanger[i].ride = false;
		cin >> t_cur_y >> t_cur_x >> t_dst_y >> t_dst_x;
		passanger[i].cur_y = t_cur_y - 1;
		passanger[i].cur_x = t_cur_x - 1;
		passanger[i].dst_y = t_dst_y - 1;
		passanger[i].dst_x = t_dst_x - 1;
		passanger[i].min_distance = min_distance(t_cur_y-1, t_cur_x-1, t_dst_y-1, t_dst_x-1);
		if(passanger[i].min_distance == -1)
		    possible = false;
	}
}

int start_taxi() {
    if(possible==false){
        return -1;
    }
	int cnt = 0;  // 승객 한 명 데려다줄 때마다 +1
	int pass, distance, temp_distance, pass_y, pass_x;
	while (cnt != M) { // 승객 다 태워줄 때까지
		distance = 10000;
		for (int i = 1; i <= M; i++) {
			if (passanger[i].ride == true) // 이미 태운 승객이면 건너뜀.
				continue;
			
			// 현재 택시와 승객 사이의 거리
			temp_distance = min_distance(taxi_y, taxi_x, passanger[i].cur_y, passanger[i].cur_x);
			if(temp_distance == -1){
			    return -1;
			}
			if (distance > temp_distance) {
				distance = temp_distance;
				pass = i;
				pass_y = passanger[i].cur_y;
				pass_x = passanger[i].cur_x;
			}
			else if (distance == temp_distance) {
				if (pass_y > passanger[i].cur_y) {
					distance = temp_distance;
					pass = i;
					pass_y = passanger[i].cur_y;
					pass_x = passanger[i].cur_x;
				}
				else if (pass_y == passanger[i].cur_y) {
					if (pass_x > passanger[i].cur_x) {
						distance = temp_distance;
						pass = i;
						pass_y = passanger[i].cur_y;
						pass_x = passanger[i].cur_x;
					}
				}
			}
		} // 승객 선정 끝.

		passanger[pass].ride = true;
		N_oil = N_oil - distance - passanger[pass].min_distance;
		cnt++;
		if(N_oil<0)
		    return -1;
		taxi_y = passanger[pass].dst_y;
		taxi_x = passanger[pass].dst_x;
		N_oil += passanger[pass].min_distance * 2; // 태워다 준 거리 2배 기름.
	}
	return N_oil;
}

int main()
{
	input();
	cout << start_taxi();
	return 0;
}

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

문제

문제

출처

ICPC

제발!! 도대체 뭐가 틀린 거죠???

ekdlemdjq456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말