글 읽기 - 예외 케이스를 모르겠습니다.

minjae200 5년 전 0

visited변수를 통하여 방문한곳을 다시한번 방문하게되면

사이클이 존재한다는 것으로 판단하고 flag를 true로 만들어주어

결과를 출력할때 -1을 출력하도록 하였습니다

모든 질문게시판에 있는 반례들을 통과하는데 어느부분에서 예외가 발생하는지 모르겠습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

char map[50][50];
bool visited[50][50];
int dp[50][50];
int dy[5] = {0,0,-1,1 };
int dx[5] = {-1,1,0,0 };
int N, M;
bool flag;

bool checkRange(int x, int y)
{
	if (0 <= x && x < N && 0 <= y && y < M) return true;
	else return false;
}

int game(int x, int y)
{
	if (flag) return -1;
	if (map[x][y] == 'H') return 0;
	if (visited[x][y]) {
		flag = true;
		return -1;
	}
	visited[x][y] = true;
	int &ret = dp[x][y];
	if (ret != -1) return ret;
	ret = 1;
	for (int i = 0; i < 4; i++) {
		int nextX = x + (dx[i]*(map[x][y]-'0'));
		int nextY = y + (dy[i]*(map[x][y]-'0'));
		if (!checkRange(nextX, nextY)) continue;
		ret = max(ret, game(nextX, nextY)+1);
	}
	visited[x][y] = false;
	return ret;
}

int main(void)
{
	memset(dp, -1, sizeof(dp));
	memset(visited, false, sizeof(visited));
	scanf("%d%d", &N, &M);
	getchar();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1c", &map[i][j]);
		}
		getchar();
	}
	int ret = game(0, 0);
	if (flag) printf("-1\n");
	else printf("%d\n", ret);
	return 0;
}

CHULMING 5년 전 2

5 7

3994995
9999999
4H99399
9999999
2993994

정답 6

님 코드 1

minjae200 5년 전 0

@CHULMING 감사합니다 :)

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

문제

문제

출처

ICPC

예외 케이스를 모르겠습니다.

minjae200 5년 전 0

CHULMING 5년 전 2

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말