AIZU-0558 Cheese

Q: 在H * W的地图上有N个奶酪工厂，每个工厂分别生产硬度为1-N的奶酪。有一只老鼠准备从出发点吃遍每一个工厂的奶酪。老鼠有一个体力值，初始时为1，每吃一个工厂的奶酪体力值增加1（每个工厂只能吃一次），且老鼠只能吃硬度不大于当前体力值的奶酪。 老鼠从当前格到上下左右相邻的无障碍物的格需要时间1单位，有障碍物的格不能走。走到工厂上时即可吃到该工厂的奶酪，吃奶酪时间不计。问吃遍所有奶酪最少用时。

 输入：第一行三个整数H(1 <= H <= 1000)、W(1 <= W <=1000)、N(1 <= N <= 9)，之后H行W列为地图， “.“为空地， ”X“为障碍物，”S“为老鼠洞， 1-N代表硬度为1-N的奶酪的工厂。输出最少用时。

注意：第一次submit时候出现了Memory Limit Exceeded,找了好长时间，以为代码写错了，结果才S B的发现原来是自己创建类时，使用的是动态申请内存，而没有进行释放，所以以后一定要注意！！千万别又踩坑了

#include <iostream>
#include <stdlib.h>
#include <queue>
#include <cstring>
#define MAX_NUM 1010
using namespace std;
int H, W, N;
bool flag[MAX_NUM][MAX_NUM] = {false};                            //标记是否已遍历过

class Node
{
public:
    Node();
    Node(int x, int y, int step);
    ~Node();
    int x;
    int y;
    int step;
};

Node::Node()
{
}

Node::Node(int x, int y, int step) {
    this->x = x;
    this->y = y;
    this->step = step;
}

Node::~Node()
{
}
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int BFS(char map[][MAX_NUM], int sx, int sy, int ex, int ey) {
    queue<Node> que;                                                  //第一次出现Memory Limit Exceeded,一定不能使用new来进行创建
    Node node(sx, sy, 0);
    que.push(node);
    flag[sx][sy] = true;                                              //将遍历的节点设置为true
    while (!que.empty())
    {
        Node cur = que.front();
        que.pop();
        if (cur.x == ex && cur.y == ey)
        {
            return cur.step;
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                int k = cur.x + dir[i][0];
                int v = cur.y + dir[i][1];
                if (k>=0&&k<H&&v>=0&&v<W&&map[k][v]!='X'&&!flag[k][v])            //将可到达并且尚未遍历的节点加入队列
                {
                    Node temp(k, v, cur.step + 1);
                    que.push(temp);
                    flag[k][v] = true;
                }
            }
        }
    }
    return -1;

}

int main()
{
    int sx, sy, arr[10][2];
    char map[MAX_NUM][MAX_NUM];
    while (cin >> H >> W >> N && H && W)
    {
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                cin >> map[i][j];
                if (map[i][j] == 'S')
                {
                    map[i][j] = '.';
                    sx = i;
                    sy = j;
                }
                if (isdigit(map[i][j]))
                {
                    int index = map[i][j] - '0';
                    arr[index][0] = i;
                    arr[index][1] = j;
                }
            }
        }
        arr[0][0] = sx;
        arr[0][1] = sy;
        int res = 0;
        for (int i = 0; i+1 <= N; i++)
        {
            memset(flag, false, sizeof(flag));
            res += BFS(map, arr[i][0], arr[i][1], arr[i + 1][0], arr[i + 1][1]);
        }
        cout << res << endl;
    }
    return 0;
}