글 읽기 - 부탁드립니다! 알려주세요!

captureit 5년 전 0

15%에서 틀렸다고 나오는데 어느 부분이 틀린건지 감이 잡히질 않습니다.

알려주시면 감사드립니다!

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#include <string>
#include <queue>
#define MAX_ROW 55
#define MAX_COL 55
#define MAX_DIR 2
using namespace std;

/*
	1). 회전조건 
	중심점을 기준으로 반경 3*3 부근에 어떠한 장애물도 없어야 한다.

	2). 회전 경우는 중심점을 (x,y) 라고 할때,
	양 쪽의 두 점이 상하로 존재하는 경우 (x-1,y), (x+1,y) 와 좌우로 존재하는 경우 (x,y-1), (x,y+1) 두 가지가 존재한다.

	3). 방문여부를 확인해는 bool 타입 배열을 visited[x][y][direction] (direction == 2)로 둔다.

*/

enum { UP_DOWN = 0, LEFT_RIGHT = 1 };

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

int N;
bool visited[MAX_ROW][MAX_COL][MAX_DIR];
char map[MAX_ROW][MAX_COL];

int end_x, end_y;
int end_dir;

struct Pos {
	int x;
	int y;
	int dir;
	int time;
	Pos(int x, int y, int dir, int time) {
		this->x = x;
		this->y = y;
		this->dir = dir;
		this->time = time;
	}
};

// 중심점 : x,y
bool isInBoundary(int x, int y, int direction) {

	for (int i = direction; i < 4; i+=2) {
		int nextX = x + dy[i];
		int nextY = y + dx[i];
		if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N || map[nextX][nextY] == '1')
			return false;
	}
	return true;
}

bool canTurn(int x, int y) {
	x = x - 1;
	y = y - 1;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			int nextX = x + j;
			int nextY = y + i;
			if (nextX < 0 || nextY < 0 || nextX>=N || nextY>=N || map[nextX][nextY] == '1')
				return false;
		}
	}
	return true;
}

int BFS(Pos start) {

	visited[start.x][start.y][start.dir] = true;

	queue<Pos> q;
	q.push(start);

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int dir = q.front().dir;
		int time = q.front().time;
		q.pop();

		if (x == end_x && y == end_y && dir == end_dir)
			return time;

		for (int i = 0; i < 4; i++) {
			int nX = x + dy[i];
			int nY = y + dx[i];
			if (!visited[nX][nY][dir] && isInBoundary(nX, nY, dir)) {
				visited[nX][nY][dir] = true;
				q.push(Pos(nX, nY, dir, time+1));
			}
		}

		if (canTurn(x, y)) {
			for (int i = 0; i < 2; i++) {
				int nDir = i;
				if (!visited[x][y][nDir] && isInBoundary(x, y, nDir)) {
					visited[x][y][nDir] = true;
					q.push(Pos(x, y, nDir, time + 1));
				}
			}
		}
	}

	return 0;
}

int main() {

	cin >> N;

	vector<pair<int, int>> start;
	vector<pair<int, int>> end;

	int direction = 0;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++) {
			map[i][j] = s.at(j);
			if (map[i][j] == 'B') 
				start.push_back(pair<int, int>(i, j));

			else if (map[i][j] == 'E') 
				end.push_back(pair<int, int>(i, j));
		}
	}

	if (start[0].first == start[1].first) direction = UP_DOWN;
	else direction = LEFT_RIGHT;

	if (end[0].first == end[1].first) end_dir = UP_DOWN;
	else end_dir = LEFT_RIGHT;

	end_x = end[1].first;
	end_y = end[1].second;

	cout << BFS(Pos(start[1].first, start[1].second, direction, 0)) << endl;
	
	return 0;
}

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

문제

문제

출처

ICPC

부탁드립니다! 알려주세요!

captureit 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말