글 읽기 - 메모리 초과

joonjeong_kr 8년 전 0

1261 문제에서 메모리 초과가 발생하는 이유를 잘 모르겠네요.

#include <cstdio>
#include <queue>

struct Point {
  int r; int c;
  Point(int r_ = 0 , int c_ = 0) : r(r_), c(c_) {}
};

char map[100][100][2];
char line[101];
/*
void dump(int n, int m) {
  for(int ni = 0; ni < n; ++ni) {
    for(int mi = 0; mi < m; ++mi) {
      printf("[%d/%d]", map[ni][mi][0], map[ni][mi][1]);
    }
    puts("");
  }
}
*/

inline int min(int a, int b) { return a < b ? a : b;}

int main() {
  int m, n;
  scanf("%d %d", &m, &n);

  for(int ni = 0; ni < n; ++ni) {
    scanf("%s", line);
    for(int mi = 0; mi < m; ++mi) {
      map[ni][mi][0] = line[mi] - '0';
      map[ni][mi][1] = 0;
    }
  }
  for(int ni = 1; ni < n; ++ni) {
    map[ni][0][1] = map[ni-1][0][1] + (map[ni][0][0] == 1 ? 1 : 0);
  }
  for(int mi = 1; mi < m; ++mi) {
    map[0][mi][1] = map[0][mi-1][1] + (map[0][mi][0] == 1 ? 1 : 0);
  }
  std::queue<Point> queue;
  queue.push(Point(0,0));
  while(!queue.empty()) {
    Point p = queue.front();
    if((p.r > 0) && (p.c > 0) && !(map[p.r][p.c][0] == 2)) {
      map[p.r][p.c][1] = min(map[p.r-1][p.c][1], map[p.r][p.c-1][1]);
      if(map[p.r][p.c][0] == 1) {
        map[p.r][p.c][1] += 1;
      }
    }
    map[p.r][p.c][0] = 2;
    if((p.r > 0) && (map[p.r-1][p.c][0] < 2)) {
      queue.push(Point(p.r-1, p.c));
    }
    if((p.r < n-1) && (map[p.r+1][p.c][0] < 2)) {
      queue.push(Point(p.r+1, p.c));
    }
    if((p.c > 0) && (map[p.r][p.c-1][0] < 2)) {
      queue.push(Point(p.r, p.c-1));
    }
    if((p.c < m-1) && (map[p.r][p.c+1][0] < 2)) {
      queue.push(Point(p.r, p.c+1));
    }

    queue.pop();
  }
  //dump(n, m);
  printf("%d\n", map[n-1][m-1][1]);
  return 0;
}

joonjeong_kr 8년 전 0

자답. queue에 쌓이는 데이터가 넘치네요

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

문제

문제

출처

ICPC

메모리 초과

joonjeong_kr 8년 전 0

joonjeong_kr 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말