글 읽기 - 시간초과 해결법좀 알려주세요 ㅜㅜㅜㅜ

sis02004 4년 전 0

마지막에 시간초과가 나는데 질문 보니까 bfs로 풀린다고 하셨는데 어떻게 고쳐야하는지 알고 싶어요ㅜㅜㅜ

#include <iostream>
#include <queue>

using namespace std;

int n, m, k;
int s_x, s_y, e_x, e_y;
char matrix[1002][1002];
int visit[1002][1002];
int d_x[4] = { -1,1,0,0 };
int d_y[4] = { 0,0,-1,1 };
bool insize(int x, int y) {
	if (x < 1 || y < 1 || x > n || y > m) {
		return false;
	}
	return true;
}
void search() {
	int cnt = 0;
	queue<pair<int, int>> q;
	visit[s_x][s_y] = 1;
	q.push(make_pair(s_x, s_y));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		if (x == e_x && y == e_y) {
			cout << visit[x][y] - 1;
			return;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int n_x = x;
			int n_y = y;
			for (int j = 0; j < k; j++) {
				n_x += d_x[i];
				n_y += d_y[i];
				if (insize(n_x, n_y) && matrix[n_x][n_y] == '.') {
					if (visit[n_x][n_y] == 0) {
						q.push(make_pair(n_x, n_y));
						visit[n_x][n_y] = visit[x][y] + 1;
					}
				}
				else {
					break;
				}
			}
		}
	}
	cout << "-1";
	return;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> matrix[i][j];
		}
	}
	cin >> s_x >> s_y >> e_x >> e_y;
	search();
}

sis02004 4년 전 1

큐에 넣는 조건을 하나 추가하여 시간을 줄여 해결했습니다.

devacver 1년 전 0

어떤 조건 추가하셨는 지 알 수 있을까요?

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

문제

문제

출처

ICPC

시간초과 해결법좀 알려주세요 ㅜㅜㅜㅜ

sis02004 4년 전 0

sis02004 4년 전 1

devacver 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말