글 읽기 - 1103 게임 질문

flflds0811 8년 전 0

사이클 체크해서 사이클 있으면 -1 출력하고 아닌경우

해당위치로부터 트리의 높이를 반환하는 dp짜서 출력하게했는데

계속 시간초과가 납니다...어디서 문제가있을까요??

ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
char arr[55][55];
bool disc[55][55];
int dp[55][55];
int xst[4] = { -1, 0, 1, 0 };
int yst[4] = { 0, 1, 0, -1 };
bool inner(int y, int x) {
	if (y >= n || y<0 || x >= m || x<0) return false;
	return arr[y][x] != 'H';
}
int dfs(int x, int y) {
	int& ret = dp[y][x];
	if (ret != -1) return ret;
	ret = 1;
	for (int i = 0; i<4; i++) {
		int nx = x + (arr[y][x] - '0')*xst[i];
		int ny = y + (arr[y][x] - '0')*yst[i];
		if (inner(ny, nx)) 
			ret = max(ret, 1 + dfs(nx, ny));
	}
	return ret;
}
bool cycle(int x, int y) {
	disc[y][x] = true;
	bool ret = false;
	for (int i = 0; i<4; i++) {
		int nx = x + (arr[y][x] - '0')*xst[i];
		int ny = y + (arr[y][x] - '0')*yst[i];
		if (inner(ny, nx)) {
			if (!disc[ny][nx]) ret |= cycle(nx, ny);
			else ret = true;
		}
		if (ret) break;
	}
	disc[y][x] = false;
	return ret;
}
int main() {
	memset(dp, -1, sizeof(dp));
	scanf("%d%d", &n, &m);
	getchar();
	for (int i = 0; i<n; i++)
		scanf("%s", &arr[i]);
	if (cycle(0, 0)) printf("-1");
	else printf("%d", dfs(0, 0));
	return 0;
}

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

문제

문제

출처

ICPC

1103 게임 질문

flflds0811 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말