글 읽기 - 같은 유형의 문제에서 통과한 소스가 해당 문제에서 런타임에러가 발생합니다.

gaelim 6년 전 0

BFS로 풀으라는 조언에 따라 BFS로 풀어보았는데요,

그전에 비슷한 유형인

BOJ의 벽 부수고 이동하기 문제에서 문제 해결을 했습니다.

아래 문제:

https://www.acmicpc.net/proble...

저의 소스코드:

https://www.acmicpc.net/submit...

다시 해당 문제로 돌아와서 같은 유형이기에

같은 접근법으로 문제를 해결하려고 했습니다만,

런타임에러가 발생하는데, 도저히 발생지점을 찾을 수가 없습니다.

문제의 조건에 따라 n==0 || m==0인 지점이 있을거같아 처리를 해주어도, 여전히 런타임 에러가 발생합니다.

도움부탁드립니다...ㅠ..ㅠ.

#include <stdio.h>
typedef struct{ int now, magic; }pos;
int n, m, sx, sy, ex, ey, a[1005][1005], d[1005][1005][2];
pos q[100000]; int h, t;
int dx[4] ={-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int min(int x, int y) { if (x<y) return x; return y;}
int main(){
  scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &ex, &ey);

  sx--, sy--, ex--, ey--;
  //if (n==0 || m==0) return printf("-1\n");
  for (int i=0; i<n; i++) for (int j=0; j<m; j++) scanf("%d", &a[i][j]);

  for (int i=0; i<n; i++)
    for (int j=0; j<m; j++)
      for (int k=0; k<=1; k++) d[i][j][k]=1<<20;

  q[t].now=sx*m+sy; q[t].magic=a[sx][sy]?0:1;
  d[sx][sy][q[t].magic]=1;
  t++;

  while (h<t){
    int now = q[h].now, magic = q[h].magic;  h++;
    int x = now/m, y = now%m;

    for (int i=0; i<4; i++){
      int nx=x+dx[i], ny= y+dy[i];
      if (nx>=0 && ny>=0 && nx<n && ny<m){

        if (!a[nx][ny]) {
          if (d[nx][ny][magic] > d[x][y][magic]+1){
            q[t].now=nx*m+ny, q[t].magic=magic, t++;
            d[nx][ny][magic]=d[x][y][magic]+1;
          }
        }
        else if (magic && d[nx][ny][0]>d[x][y][magic]+1){
          q[t].now=nx*m+ny; q[t].magic=0; t++;
          d[nx][ny][magic-1]=d[x][y][magic]+1;
        }
      }
    }
  }

  if (d[ex][ey][1]!=(1<<20) || d[ex][ey][0]!=(1<<20))
    printf("%d\n", min(d[ex][ey][1], d[ex][ey][0])-1);
  else printf("-1\n");
}

gaelim 6년 전 0

재밌는건, 3%에서 런타임 에러가 뜨며,

C++로 제출하면 3%에서 틀렸다고 뜹니다. 도대체 무엇이 다른걸까요 ...ㅠㅠ..

Green55 6년 전 1

소스를 제대로 이해한건지 잘 모르겠는데, q를 큐로 쓰고있는거 맞나요?

최대 1000*1000*2 = 2,000,000의 상태가 큐에 들어 갈 수 있는데 q의 메모리는 100,000 밖에 배당하지 않은거지 문제이지 않을까 싶습니다.

gaelim 6년 전 0

아 감사합니다 문제바로 해결했습니다 항상 bfs 문제풀때 관대하게 q 크기를 작게잡았어요... 이런이런 ㅠ.ㅠ 감사합니다 덕분에 해결했어요

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

문제

문제

출처

ICPC

같은 유형의 문제에서 통과한 소스가 해당 문제에서 런타임에러가 발생합니다.

gaelim 6년 전 0

gaelim 6년 전 0

Green55 6년 전 1

gaelim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말