글 읽기 - c++ 왜 틀렸는지 모르겠습니다.

celestial 2년 전 0

방향이 다를 때에는 같은 방향으로 이동하는 명령에 대한 처리를 위해 + 2를 하고

방향이 같고 길을 이동할 수 있을 때에는 그냥 큐에 넣는 방식으로 처리를 했습니다.

도착점에 대한 방문처리를 따로 하지 않아서 이후 큐에 들어올 최적의 해가 나올 것을 염두하여

계속 최적을 갱신하도록 코드를 작성해보았는데

어디가 틀린건지 잘 모르겠습니다ㅜㅜ

도와주시면 정말 감사합니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define MAX 101

using namespace std;


int M, N;

int map[MAX][MAX];
bool visited[MAX][MAX];

typedef struct robot {
	int x;
	int y;
	int dir = 0;
	int ordercnt = 0;
}Robot;

Robot start;
Robot target;


queue<Robot>Q;


int dx[] = { 0,0,0,1,-1 };
int dy[] = { 0,1,-1,0,0 };

int sx, sy, sd;
int tx, ty, td;

int res = 10000;
void BFS(Robot start) {
	
	Robot current;
	while (!Q.empty()) {
		current = Q.front();
		Q.pop();
		//printf("front x : %d y : %d dir : %d ordercnt : %d \n\n", current.x, current.y, current.dir, current.ordercnt);
		if (current.x == target.x && current.y == target.y) {
			//printf("도착 : current x : %d y : %d dir : %d ordercnt : %d res : %d \n\n", current.x, current.y, current.dir, current.ordercnt,res);
			if (current.dir == target.dir) {
				res = min(res, current.ordercnt);
			}
			if (current.dir != target.dir) {
				current.dir = target.dir;
				current.ordercnt++;
				res = min(res, current.ordercnt);
				
			}
			
			
			
		}



		for (int i = 1; i < 5; i++) {

			int nextdirection = i;
			int nx = current.x + dx[i];
			int ny = current.y + dy[i];
			int currentdirection = current.dir;
			
			
			if (nx >= 1 && nx <= M && ny >= 1 && ny <= N && !visited[nx][ny]) {

				if (map[nx][ny] == 0 && nextdirection == currentdirection) {
					Robot next;
					next.x = nx;
					next.y = ny;
					next.dir = nextdirection;
					next.ordercnt = current.ordercnt;
					visited[nx][ny] = true;
					if (nx == target.x && ny == target.y) { visited[nx][ny] = false; }
					//printf("next x : %d y : %d dir : %d ordercnt : %d \n\n", next.x, next.y, next.dir, next.ordercnt);
					Q.push(next);
				}
				if (map[nx][ny] == 0 && nextdirection != currentdirection) {
					Robot next;
					next.x = nx;
					next.y = ny;
					next.dir = nextdirection;
					next.ordercnt = current.ordercnt + 2;
					visited[nx][ny] = true;
					if (nx == target.x && ny == target.y) { visited[nx][ny] = false; }
					//printf("next x : %d y : %d dir : %d ordercnt : %d \n\n", next.x, next.y, next.dir, next.ordercnt);
					Q.push(next);

				}


			}
			
		}





	}



}




int main() {

	//M 세로 N 가로
	cin >> M >> N;

	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}

	
	cin >> start.x >> start.y >> start.dir;
	cin >> target.x >> target.y >> target.dir;
	/*printf("start x : %d y : %d dir : %d ordercnt : %d \n\n", start.x, start.y, start.dir, start.ordercnt);
	printf("target x : %d y : %d dir : %d ordercnt : %d \n\n", target.x, target.y, target.dir, target.ordercnt);*/
	visited[start.x][start.y] = true;
	Q.push(start);
	BFS(start);

	printf("%d",res);



}

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

문제

문제

출처

ICPC

c++ 왜 틀렸는지 모르겠습니다.

celestial 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말