글 읽기 - 고수님들 도와주세요 ㅠㅠㅠ

minerba 5년 전 0

이문제 반례가 어떤게 있는지 모르겠습니다... ㅠㅠ

큐에 이동가능한 지점들을 다 넣어주면서 탐색했습니다만 ㅠㅠㅠ

도와주시면 감사하겠습니다.

#include<iostream>
#include<queue>
#define N 1001 

using namespace std;

int n, m, r, x1, x2, y3, y2;  char map[N][N];
bool chk[N][N]; queue<pair<int, int>> q;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m >> r;

	for (int i = 0; i < n; i++) cin >> map[i];
	cin >> x1 >> y3 >> x2 >> y2;
	x2 -= 1; y2 -= 1;
	q.push({ x1-1, y3-1 });
	int sec = 0;
	while (!q.empty()) {
		int sz = q.size();
		for (int k = sz; k--;) {
			int xx = q.front().first; int yy = q.front().second;
			q.pop();
			chk[xx][yy] = true; 
			if (xx == x2 && yy == y2) {
				cout << sec << '\n'; 
				return 0; 
			}
			for (int i = 0; i < 4; i++) {
				int nx = xx + dx[i]; int ny = yy + dy[i]; 
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 
				if (map[nx][ny] != '.') continue;  int mo = 1;
				while (mo <= r && nx >= 0 && nx < n && ny >= 0 && ny < m && !chk[nx][ny] && map[nx][ny] == '.') {
					//cout << nx << ' ' << ny << '\n'; 
					q.push({ nx, ny }); 
					chk[nx][ny] = true; 
					nx += dx[i]; ny += dy[i]; 
					mo++; 
				}
			}
		}
		sec++;
	}
	cout << -1 << '\n'; 

	return 0;
}

upple1 5년 전 0

같은 시간대에 특정 지점을 세로로 지나가는 경우와 가로로 지나가는 경우가 있는데

만약 세로로 먼저 지나갔다고 생각한다면

가로로 지나갈 때 더 적은 시간이 소요됨에도 불구하고 세로로 먼저 지나갔기 때문에 지나가지 못하게 됩니다.

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

문제

문제

출처

ICPC

고수님들 도와주세요 ㅠㅠㅠ

minerba 5년 전 0

upple1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말