글 읽기 - C언어 실행은 다 되는데 시간초과...

mywoospam 1년 전 0

찾아본 모든 예제들이 실행됩니다.

시간초과가 날 이유도 없는거 같은데 해결책이 있을까요..

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int map[1000][1000];
int chk[1000][1000][2];
int n, m, nextX,nextY;

typedef struct queue {
	int x, y, wall, depth;
}queue;

queue node[10000];

int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int st = -1, ed = -1;

int isArea(int x, int y){
	if (x > 0 && y > 0 && x <= n && y <= m)
		return 1;
	else
		return 0;
}

int BFS(void) {
	node[++ed].x = 1;
	node[ed].y = 1;
	node[ed].wall = 0;
	node[ed].depth = 1;
	chk[1][1][0] = 1;
	while (st != ed) {
		if (node[++st].x == n && node[st].y == m) {
			printf("%d", node[st].depth);
			return 1;
		}
		for (int i = 0; i < 4; i++) {
			nextX = node[st].x + dx[i];
			nextY = node[st].y + dy[i];
			if (map[nextX][nextY] == 0 && isArea(nextX, nextY) && chk[nextX][nextY][node[st].wall] == 0) {
				node[++ed].x = nextX;
				node[ed].y = nextY;
				node[ed].wall = node[st].wall;
				node[ed].depth = node[st].depth + 1;
				chk[nextX][nextY][node[st].wall] = 1;
			}
			else if (map[nextX][nextY] == 1 && isArea(nextX, nextY) && chk[nextX][nextY][1] == 0 && node[st].wall == 0) {
				node[++ed].x = nextX;
				node[ed].y = nextY;
				node[ed].wall = node[st].wall+1;
				node[ed].depth = node[st].depth + 1;
				chk[nextX][nextY][1] = 1;
			}
		}
	}
	printf("-1");
}

int main(void) {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			scanf("%1d", &map[i][j]);
	}
	BFS();
}

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

문제

문제

출처

ICPC

C언어 실행은 다 되는데 시간초과...

mywoospam 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말