글 읽기 - 게시판에서 반례를 다 찾아서 넣어보았으나.... 결국 해결하지 못했습니다..

isg1031 4년 전 0

cin 입력을 전부 문자로 입력받아 이용하는 방식입니다.

예제, 게시판에서 찾은 반례들을 넣어도 정답으로 나오지만 결국 틀립니다... 반례를 못찾겠습니다...

도움이 필요합니다 TvT...

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<char>> arr;
vector<vector<bool>> discovered;
int N, M;
const int directX[4] = {0, 1, 0, -1};	//상, 우, 하, 좌
const int directY[4] = {-1, 0, 1, 0};


void bfs() {	//0, 0에서 부터 출발
	queue<pair<pair<char, char>, int>> q;
	q.push(make_pair(make_pair('0', '0'), 1));	//(Y, X), depth

	while (!q.empty()) {
		char hereX = q.front().first.second;
		char hereY = q.front().first.first;
		int depth = q.front().second;
		q.pop();

		++depth;
		for (int k = 0; k < 4; ++k) {
			int thereX = hereX - '0' + directX[k];    //문자 -> 정수형
			int thereY = hereY - '0' + directY[k];    
			if (thereX < 0 || thereX >= M || thereY < 0 || thereY >= N)
				continue;
			if (thereX == M - 1 && thereY == N - 1) {    //Result
				cout << depth << '\n';
				return;
			}
			if (arr[thereY][thereX] == '1' && !discovered[thereY][thereX]) {
				q.push(make_pair(make_pair(thereY + '0', thereX + '0'), depth));    //정수 -> 문자
				discovered[thereY][thereX] = true;
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N >> M;
	arr = vector<vector<char>>(N, vector<char>(M));
	discovered = vector<vector<bool>>(N, vector<bool>(M, false));

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> arr[i][j];
		}
	}
	bfs();
}

djm03178 4년 전 0

좌표를 저장하는 범위에 문제가 있습니다.

애초에 좌표를 굳이 문자로 저장할 필요가 있을까요?

2 100
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

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

문제

문제

출처

ICPC

게시판에서 반례를 다 찾아서 넣어보았으나.... 결국 해결하지 못했습니다..

isg1031 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말