글 읽기 - 이 알고리즘의 반례가 어떻게 되나요?

titane308 5년 전 0

테스트 케이스들은 모두 통과하는데 어떨 때 틀리는 걸까요?

#include <iostream>
#include <queue>
#include <tuple>
#include <cstdio>
using namespace std;

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

int main()
{
	int n, m, l;
	cin >> n >> m >> l;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &a[i][j]);
		}
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) d[i][j] = -1;
	queue<tuple<int, int, int>> q;
	q.emplace(0, 0, 0);
	d[0][0] = 1;
	bool found = false;
	int ans = -1;
	while (!q.empty())
	{
		int x, y, c;
		tie(x, y, c) = q.front(); q.pop();
		for (int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
			if (nx == m - 1 && ny == n - 1)
			{
				ans = d[y][x] + 1;
				found = true;
				break;
			}
			if (a[ny][nx] == 1 && c + 1 > l) continue;
			if (d[ny][nx] != -1) continue;
			if (a[ny][nx] == 1 && c + 1 <= l)
			{
				d[ny][nx] = d[y][x] + 1;
				q.emplace(nx, ny, c + 1);
			}
			if (a[ny][nx] == 0)
			{
				d[ny][nx] = d[y][x] + 1;
				q.emplace(nx, ny, c);
			}
		}
		if (found) break;
	}
	cout << ans << '\n';
}

luniro 5년 전 6

반례

정답: 16

출력: -1

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

문제

문제

출처

ICPC

이 알고리즘의 반례가 어떻게 되나요?

titane308 5년 전 0

luniro 5년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말