글 읽기 - 잘못된 테스트 케이스 머가 있을까요??

wlsgns888 5년 전 0

통나무 가운데 위치와 방향(가로,세로) 방향 구분하여 BFS를 사용하였습니다.

그런데 잘못된 테스트케이스를 찾기가 힘드네요 ㅠㅠ

잘못된 테스트케이스 머가 있을까요??

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
int map[50][50];
int visited[50][50][2];
int dx[5] = { 0, 0, -1, 1, 0 }; 
int dy[5] = { -1, 1, 0, 0, 0 };

bool check(int y, int x, int dir, int d){
	vector<pair<int, int> > vec;
	if (d == 0){
		if (dir = 0)
		for (int i = 0; i < 3; i++)
			vec.push_back(make_pair(y - 1, x - 1 + i));
		else
			vec.push_back(make_pair(y - 2, x));
	}
	else if (d == 1){
		if (dir == 0)
		for (int i = 0; i < 3; i++)
			vec.push_back(make_pair(y + 1, x - 1 + i));
		else
			vec.push_back(make_pair(y + 2, x));
	}
	else if (d == 2){
		if (dir == 0)
			vec.push_back(make_pair(y, x - 2));
		else
		for (int i = 0; i < 3; i++)
			vec.push_back(make_pair(y - 1 + i, x - 1));
	}
	else if (d==3)
	if (dir == 0)
		vec.push_back(make_pair(y, x + 2));
	else
	for (int i = 0; i < 3; i++)
		vec.push_back(make_pair(y - 1 + i, x + 1));
	else{
		if (dir == 0)
		for (int i = 0; i < 3; i++){
			vec.push_back(make_pair(y - 1, x - 1 + i));
			vec.push_back(make_pair(y + 1, x - 1 + i));
		}
		else
		for (int i = 0; i < 3; i++){
			vec.push_back(make_pair(y - 1 + i, x - 1));
			vec.push_back(make_pair(y - 1 + i, x + 1));
		}
	}

	for (int i = 0; i < vec.size(); i++){
		int ny = vec[i].first;
		int nx = vec[i].second;
		if (ny < 0 || nx < 0 || ny >= n || nx >= n || map[ny][nx] == 1)
			return false;
	}
	return true;

}



int main(void)
{
	freopen("input.txt", "r", stdin);
	cin >> n;
	vector<pair<int, int> > BBB;
	vector<pair<int, int> > EEE;
	for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++){
		char tmp; int tmp_i;
		cin >> tmp;
		tmp_i = 0;
		if (tmp == '1')
			tmp_i = 1;
		else if (tmp == 'B')
			BBB.push_back(make_pair(i, j));
		else if (tmp == 'E')
			EEE.push_back(make_pair(i, j));
		map[i][j] = tmp_i;
	}
	pair<pair<int, int>, int> st; // 통나무 시작 가운데 y, x 방향
	pair<pair<int, int>, int> dst; //도착 통나무
	st.first.first = BBB[1].first;
	st.first.second = BBB[1].second;
	if (BBB[1].second + 1 == BBB[2].second)
		st.second = 0;
	else
		st.second = 1;
	dst.first.first = EEE[1].first;
	dst.first.second = EEE[1].second;
	if (EEE[1].second + 1 == EEE[2].second)
		dst.second = 0;
	else
		dst.second = 1;

	
	queue < pair<pair<int, int>, int> > q;
	q.push(st);
	visited[st.first.first][st.first.second][st.second] = 1;
	int cnt = 0;
	if (st == dst){
		cout << "0";
		return 0;
	}
	while (!q.empty()){
		int q_size = q.size();
		for (int i = 0; i < q_size; i++){
			int cy = q.front().first.first;
			int cx = q.front().first.second;
			int cd = q.front().second;
			q.pop();
			for (int j = 0; j < 5; j++){
				int ny = cy + dy[j];
				int nx = cx + dx[j];
				int nd = cd;
				if (j == 4 && cd == 0)
					nd = 1;
				else if (j==4 && cd==1)
					nd = 0;
				if (check(cy, cx, cd, j) && !visited[ny][nx][nd]){
					visited[ny][nx][nd] = 1;
					q.push(make_pair(make_pair(ny, nx), nd));
				}
			}
		}
		cnt++;
		if (visited[dst.first.first][dst.first.second][dst.second])
			break;
	}

	if (visited[dst.first.first][dst.first.second][dst.second])
		cout << cnt;
	else
		cout << "0";

}

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

문제

문제

출처

ICPC

잘못된 테스트 케이스 머가 있을까요??

wlsgns888 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말