글 읽기 - 2178 bfs 틀렸습니다

swhotlsw 4년 전 0

예제 테스트케이스 통과합니다. 어느 부분이 틀렸는지 모르겠습니다.ㅠ

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

queue <pair<char,char>> q;
bool check[102][102] = { false, };
string arr[102] = {};
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int cnt = 0;
int n, m;

void bfs(int start_x, int start_y) {
	q.push(make_pair(start_x, start_y));
	check[start_x][start_y] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		if (x == n - 1 && y == m - 1) break;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if (cx >= 0 && cx < n && cy >= 0 && cy < m && arr[cx][cy]=='1' && check[cx][cy]== false) {
				q.push(make_pair(cx, cy));
				check[cx][cy] = true;
				int change = arr[x][y]-'0'+1;
				arr[cx][cy] = change + '0';
			}
		}
	}
}

int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	bfs(0,0);
	int res = arr[n - 1][m - 1] - '0';
	cout << res;
	return 0;
}

hayman42 4년 전 1

미로가 s 자로 구불구불하면 change 값은 char 범위를 충분히 넘을수 있는데, 그 값을 arr[cx][cy] 에다 넣어서 오버플로우가 일어 날 것 같습니다. 거리를 저장할 배열을 굳이 string 의 배열로 저장할 필요는 없을 것 같아요.

swhotlsw 4년 전 0

감사합니다. char 오버플로우에 대해 생각해보지 못했는데 hayman42님 덕분에 해결했습니다.

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

문제

문제

출처

ICPC

2178 bfs 틀렸습니다

swhotlsw 4년 전 0

hayman42 4년 전 1

swhotlsw 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말