ghostbody / 15-cpp-learning

15 c++ learning repository of SDCS SYSU
6 stars 3 forks source link

Memory Limit. #21

Open JohnTargaryen opened 8 years ago

JohnTargaryen commented 8 years ago

morning +7, in the maze problem, i 've tried my ways like only declare 2 struct variable temp and another to store the data, and modify them if needed, so as to avoid the memory limit exceeded issue. There occurs still,however, when the input gets big, memory limit.Could you gimme some advice on avoiding memory limit based on my code below?please. Thank you.

#include <iostream>
#include <queue>

using namespace std;

struct one {
  int ro, co, depth;
  one(int r, int c, int d) : ro(r), co(c), depth(d) {}
  one operator()(int r, int c, int d) {
    ro = r;
    co = c;
    depth = d;
    return *this;
  }
};

int main() {
  int row, col, srow, scol, erow, ecol, nowr, nowc;
  char maze[20][20];
  cin >> row >> col;
  for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
      cin >> maze[i][j];
      if (maze[i][j] == 'S') {
        srow = i;
        scol = j;
      }
      else if (maze[i][j] == 'E') {
        erow = i;
        ecol = j;
      }
    }
  }
  one temp(0, 0, 0);
  one another(0, 0, 0);
  queue<one> q;
  q.push(another(srow, scol, 0));
  maze[srow][scol] = '#';
  while (!q.empty()) {
    temp = q.front();
    q.pop();
    nowr = temp.ro;
    nowc = temp.co;
    if (maze[nowr][nowc] == 'E') {
      cout << temp.depth << endl;
      return 0;
    } else {
        maze[nowr][nowc] = '#';
    if (maze[nowr - 1][nowc] != '#' && maze[nowr - 1][nowc] != '!') {
      q.push(another(nowr - 1, nowc, temp.depth + 1));
    }
    if (maze[nowr + 1][nowc] != '#' && maze[nowr + 1][nowc] != '!') {
      q.push(another(nowr + 1, nowc, temp.depth + 1));
    }
    if (maze[nowr][nowc - 1] != '#' && maze[nowr][nowc - 1] != '!') {
      q.push(another(nowr, nowc - 1, temp.depth + 1));
    }
    if (maze[nowr][nowc + 1] != '#' && maze[nowr][nowc + 1] != '!') {
      q.push(another(nowr, nowc + 1, temp.depth + 1));
    }
    }
  }
  cout << "-1" << endl;
}