글 읽기 - 시간초과 해결법을 모르겠습니다.

whdtls3878 5년 전 0

BFS 로 풀면 충분히 돌아갈꺼같아서 돌려봤는데

자꾸 시간초과가 납니다 ㅠㅠ 조언 부탁드립니다.

#include <iostream>
#include <queue>
#define MAX 1002
using namespace std;
struct xyc { int x;	int y; int cnt; };
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
char map[MAX][MAX];
bool visit[MAX][MAX];
int n, m, k;
int startX, startY, defX, defY;
int checkRange(int x, int y) { return (1 <= x && x <= n && 1 <= y && y <= m); }
void bfs() {
	queue<xyc> Jin;
	Jin.push({ startX ,startY ,0 });
	visit[startX][startY] = true;
	while (!Jin.empty()) {
		xyc cur = Jin.front();
		Jin.pop();
		if (cur.x == (defX) && cur.y == (defY )) {
			cout << cur.cnt << "\n";
			return;
		}
		for (int j = 0; j < 4; j++) {
			xyc tmp = cur;
			for (int l = 0; l < k; l++) {
				int nextX = tmp.x + dx[j];
				int nextY = tmp.y + dy[j];
				if (checkRange(nextX, nextY) && map[nextX][nextY] == '.') {
					if (!visit[nextX][nextY]) {
						visit[nextX][nextY] = true;
						Jin.push({ nextX,nextY,cur.cnt + 1 });
					}
					tmp.x = nextX;	tmp.y = nextY;
				}
				else break;
			}
		}
	}
	cout << -1 << "\n";
	return;
}
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)	for (int j = 1; j <= m; j++) cin >> map[i][j];
	cin >> startX >> startY >> defX >> defY;
	bfs();
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 해결법을 모르겠습니다.

whdtls3878 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말