글 읽기 - 틀렸습니다... 왜 틀렸을까요...

mimmyum 7년 전 0

질문에 있는 테스트 케이스같은것도 다 확인하고, 직접 돌아갈때는 잘 돌아가는 것 같은데

시간초과도 아니고 틀렸습니다가 나옵니다...

왜 틀렸을까요...

H가 들어갈때는 0으로 넣고, 상,좌,하,우 방향을 순서대로 탐색하도록 했는데 다른 분들 코드에서 dfs면 시간초과라는데 저는 아예 틀렸습니다가 나와서 뭐가 잘못됐는지 정확히 모르겠습니다... ㅠ.ㅠ

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct POINT {
	int x;
	int y;
};

struct MATRIX {
	int number;
	struct POINT way[4]; // 0 위쪽 1 왼쪽 2아래쪽 3오른쪽
	int visited;
};

void DFS(int x, int y, struct MATRIX ** B);
int move = 0, max_move = 0, move_infinite = 0;
int s_now = 0;

int main() {
	int N = -1, M = -1;
	int i, j, k;
	struct MATRIX **BOX;
	struct POINT coin, *stack;


	while (N < 0 || N>50)
		scanf("%d", &N);
	while (M < 0 || M>50)
		scanf("%d", &M);
	//N은 세로, M은 가로

	BOX = (struct MATRIX**)malloc(sizeof(struct MATRIX*)*N);
	for (i = 0; i < N; i++)
		BOX[i] = (struct MATRIX*)malloc(sizeof(struct MATRIX)*M);

	stack = (struct POINT*)malloc(sizeof(struct POINT)*100000);

	for (i = 0; i < N; i++) {
		char *string;
		string = (char*)malloc(sizeof(char)*M);
		scanf("%s",string);
		j = 0;
		while (j != M) {
			char cpy;
			strncpy(&cpy, &string[j], sizeof(char));
			BOX[i][j].number = atoi(&cpy);
			BOX[i][j].visited = 0;
			j++;
		}
	}
	// 입력완료

	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++) {
			if (BOX[i][j].number == 0) {
				for (k = 0; k < 4; k++) {
					BOX[i][j].way[k].x = -1;
					BOX[i][j].way[k].y = -1;
				}
			}
			else {
				for (k = 0; k < 4; k++) {
					switch (k) {
					case 0:
						if (i - BOX[i][j].number >= 0) {
							BOX[i][j].way[0].x = i - BOX[i][j].number;
							BOX[i][j].way[0].y = j;
						}
						else {
							BOX[i][j].way[0].x = -1;
							BOX[i][j].way[0].y = -1;
						}
						break;
					case 1:
						if (j - BOX[i][j].number >= 0) {
							BOX[i][j].way[1].x = i;
							BOX[i][j].way[1].y = j - BOX[i][j].number;
						}
						else {
							BOX[i][j].way[1].x = -1;
							BOX[i][j].way[1].y = -1;
						}
						break;
					case 2:
						if (i + BOX[i][j].number <= N-1) {
							BOX[i][j].way[2].x = i + BOX[i][j].number;
							BOX[i][j].way[2].y = j;
						}
						else {
							BOX[i][j].way[2].x = -1;
							BOX[i][j].way[2].y = -1;
						}
						break;
					case 3:
						if (j + BOX[i][j].number <= M-1) {
							BOX[i][j].way[3].x = i;
							BOX[i][j].way[3].y = j + BOX[i][j].number;
						}
						else {
							BOX[i][j].way[3].x = -1;
							BOX[i][j].way[3].y = -1;
						}
					}
				}
			}
		}

	coin.x = 0; coin.y = 0;
	stack[s_now].x = 0;
	stack[s_now++].y = 0;

	DFS(0, 0, BOX);

	if (move_infinite == 1)
		printf("-1\n");
	else
		printf("%d\n", max_move);

	return 0;
}

void DFS(int x, int y, struct MATRIX **B) {
	int k;
	
	B[x][y].visited = 1;

	for (k = 0; k < 4; k++) {
		if (B[x][y].way[k].x != -1 ) {
			if (B[B[x][y].way[k].x][B[x][y].way[k].y].visited == 1) {
				move_infinite = 1;
				return;
			}
			if (B[B[x][y].way[k].x][B[x][y].way[k].y].number == 0) {
				move++;
				if (move > max_move)
					max_move = move;
				move--;
				continue;
			}
		move++;
		if (move > max_move)
			max_move = move;

		DFS(B[x][y].way[k].x, B[x][y].way[k].y, B);
		}
		move++;
		if (move > max_move)
			max_move = move;
		move--;
	}
	move--;
	B[x][y].visited = 0;

}

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

문제

문제

출처

ICPC

틀렸습니다... 왜 틀렸을까요...

mimmyum 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말