글 읽기 - 미로탐색 틀렸습니다가 나오네요 도와주세요!

2015112119 5년 전 0

큐와 pair를 이용해 bfs로 문제를 풀어보려고 했으나 틀렸다고 나오네요 예시와 반례는 정답이 나오고요

어디가 틀렸는지 잘 모르겠습니다.

칸이 1이라 이동가능한경우, 한번도 이동하지않은경우 그리고 칸 내부의 조건하에

visited로 칸이 움직일때마다 이동한 회수를 저장해주었구요 bfs를 돌려보았지만 저는 모르겠네요

뭐가 문제일걸까요?

#include <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
#include <algorithm>
#include <math.h>

using namespace std;

int n, m, arr[100][100], visited[100][100], cnt=1;
queue<pair<int, int>> vec;

#define inside x >= 0 && y >= 0 && x < n && y < m

int bfs(int x, int y) {
	
	visited[x][y] = 1;
	vec.push(pair<int, int>(x, y));

	while (!vec.empty()) {
		x = vec.front().first;
		y = vec.front().second;
		vec.pop();
		
		if (x == n - 1 && y == m - 1) break;

		if (inside && arr[x + 1][y] == 1 && visited[x + 1][y]==-1) {
			visited[x + 1][y] = visited[x][y] + 1;
			vec.push(pair<int, int>(x + 1, y));
		}if (inside && arr[x][y + 1] == 1 && visited[x ][y + 1] == -1) {
			visited[x][y + 1] = visited[x][y] + 1;
			vec.push(pair<int, int>(x, y + 1));
		}if (inside && arr[x - 1][y] == 1 && visited[x - 1][y] == -1) {
			visited[x - 1][y] = visited[x][y] + 1;
			vec.push(pair<int, int>(x - 1, y));
		}if (inside && arr[x][y - 1] == 1 && visited[x][y - 1] == -1) {
			visited[x][y - 1] = visited[x][y -1] + 1;
			vec.push(pair<int, int>(x, y - 1));
		}
	}

	return visited[x][y];
}

int main() {
	memset(visited, -1, sizeof(visited));
	memset(arr, -1, sizeof(arr));
	scanf("%d%d", &n, &m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
			if (arr[i][j] == 0) visited[i][j] = 0;
		}
	}

	cout << bfs(0, 0);
}