正在做一道普通的BFS遍歷題目，題目鏈接如下：
http://codeup.cn/problem.php?cid=100000609&pid=1
大概題意是給定一個8*8地圖，有一些障礙，從左下角起點到右上角終點，有一些障礙物，每走一步障礙物落下一格。求給定的用例，能否使得自己走到終點。
通常的做法是BFS佇列遍歷，模板做法，網上也有很多類似的解法。
附一個參考題解：https://blog.csdn.net/qq_43337016/article/details/97284156
我的代碼如下（只是先貼出來，后面會詳細描述我的問題）：
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
typedef struct Node {
int x;
int y;
int step;
// bool stone[10][10];
Node(int _x, int _y) : x(_x), y(_y), step(0) {}
Node(int _x, int _y, int _step) : x(_x), y(_y), step(_step) {}
} Node;
int T;
char map[10][10];
bool stone[10][10];
int dx[9] = {0, -1, 1, 0, 0, -1, -1, 1, 1};
int dy[9] = {0, 0, 0, -1, 1, -1, 1, -1, -1};
bool flag;
void bfs() {
queue<Node> q;
q.push(Node(7, 0, 0));
while (!q.empty()) {
Node now = q.front();
q.pop();
for (int i = 0; i < 9; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if (stone[nx - now.step][ny]) continue;
if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8) continue;
if (stone[nx - now.step - 1][ny]) continue;
if (map[nx][ny] == 'A' || now.step > 8) {
flag = true;
return;
}
Node tmp = Node(nx, ny, now.step + 1);
q.push(tmp);
}
}
}
int main() {
scanf("%d", &T);
int cnt = 1;
while (T--) {
for (int i = 0; i < 8; i++) {
scanf("%s", map[i]);
}
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (map[i][j] == 'S') {
stone[i][j] = true;
}
}
}
bfs();
if (flag) {
printf("Case #%d: Yes\n", cnt);
}
else {
printf("Case #%d: No\n", cnt);
}
cnt++;
flag = false;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
stone[i][j] = false;
}
}
}
return 0;
}
其中，while回圈內的for回圈，是搜索接下來的每一種情況并儲存到佇列中。但是在條件判斷的時候遇到了問題：
for (int i = 0; i < 9; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if (stone[nx - now.step][ny]) continue;
if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8) continue;
if (stone[nx - now.step - 1][ny]) continue;
if (map[nx][ny] == 'A' || now.step > 8) {
flag = true;
return;
}
Node tmp = Node(nx, ny, now.step + 1);
q.push(tmp);
}
在
if (stone[nx - now.step][ny]) continue;
...
if (stone[nx - now.step - 1][ny]) continue;
這兩個陳述句中，判斷當前位置是否會碰到石頭。stone是bool型陣列，存放了題目中石頭的位置。
我的解法是沒有問題的，但是在提交的時候會報記憶體超限，超過128MB。
但如果我把stone陣列換成map陣列（即輸入時儲存的地圖），判斷位置上的點是否有'S'存在，則能夠滿分通過。記憶體為大約6MB。
我知道沒有必要單獨開一個bool陣列來儲存石頭位置，但是不明白為什么會爆記憶體。
還請高手指點！謝謝
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/218874.html
標籤：C++ 語言
下一篇：提問 關于二維陣列呼叫的問題