글 읽기 - 1103 BFS로 풀어봤는데 어느 부분이 틀렸는지 모르겠습니다.

yomyom0824 5년 전 0

질문에 올라온 케이스들은 전부 통과하는데 어느 부분에서 논리가 잘못됐는지 모르겠습니다. 꼭 도와주세요 ... ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <math.h>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <regex>
#include <sstream>
#include <utility>
#include <list>

using namespace std;

char mp[55][55];

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

struct s {
	int y, x, cnt;
	bool chk[55][55];
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> mp[i][j];

	queue<s> q;
	s temp;
	temp.y = 0;
	temp.x = 0;
	temp.cnt = 1;
	memset(temp.chk, 0, sizeof(temp.chk));
	temp.chk[0][0] = true;
	q.push(temp);

	int max_cnt = 1;

	while (!q.empty()) {
		s pos = q.front();
		q.pop();

		int l = mp[pos.y][pos.x] - '0';

		for (int dir = 0; dir < 4; dir++) {
			int ny = pos.y + dy[dir] * l, nx = pos.x + dx[dir] * l;
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || mp[ny][nx] == 'H') continue;
			
			if (pos.chk[ny][nx]) { cout << -1 << '\n'; return 0; }

			pos.chk[ny][nx] = true;
			s temp;
			temp.y = ny;
			temp.x = nx;
			temp.cnt = pos.cnt + 1;
			for (int a = 0; a < n; a++)for (int b = 0; b < m; b++) temp.chk[a][b] = pos.chk[a][b];
			q.push(temp);
			max_cnt = max(pos.cnt + 1, max_cnt);
		}
	}

	cout << max_cnt << endl;


	return 0;

}

djm03178 5년 전 0

67번째 줄에서 true로 바꾼 것은 이후의 다른 방향에 대해서는 적용되지 않아야 합니다.

5 5
4HHH9
HHHHH
HHH12
HHHHH
3HH2H
정답: 6
출력: -1

yomyom0824 5년 전 0

감사합니다! 결국 또 메모리 초과네요. dfs로 풀이를 바꿔야 하겠습니다.ㅠㅠ

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

문제

문제

출처

ICPC

1103 BFS로 풀어봤는데 어느 부분이 틀렸는지 모르겠습니다.

yomyom0824 5년 전 0

djm03178 5년 전 0

yomyom0824 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말