ICPC 国内予選 2010 B: 迷図と命ず MLEエラー

Question

AOJの「迷図と命ず」をc++で回答しているのですが、「Memory limit exceeded」エラーが発生してしまいます。通常の幅優先探索と比べて大きな配列を使っているわけではないと思うのですが、原因お分かりの方いれば教えていただきたいです。

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> WallVertical;
vector<vector<int>> WallHorizon;
vector<vector<int>> seen;
int main() {
    while(true){
        int w,h;
        cin >> w >> h;
        if(w == 0 && h == 0)break;

        vector<int> temp1(w-1,0);
        WallVertical.assign(h,temp1);
        vector<int> temp2(w,0);
        WallHorizon.assign(h-1,temp2);

        for(int i = 0; i < h; i++){
            for(int j = 0; j < w-1; j++){
                cin>>WallVertical.at(i).at(j);
            }
            if(i == h-1)break;
                

            for(int j = 0; j < w; j++){
                cin>>WallHorizon.at(i).at(j);
            }
        }

        vector<int> temp3(w,-1);
        seen.assign(h,temp3);

        vector<pair<int,int>> nextWatch = {make_pair(0,0)};

        int counter = 1;
        while(nextWatch.size()){
            vector<pair<int,int>> nextWatch_temp;
            for(auto pixel : nextWatch){
                seen.at(pixel.first).at(pixel.second) = counter;
                int x,y;
                bool flag;

                x = pixel.first-1;
                y = pixel.second;
                flag = true;
                if(x < 0 || x >= h)flag = false;
                if(y < 0 || y >= w)flag = false;
                if(flag){
                    // cout << "aaaa" << endl;
                    if(seen.at(x).at(y) == -1 && !(WallHorizon.at(x).at(y))){
                        nextWatch_temp.push_back(make_pair(x,y));
                    }
                }

                x = pixel.first+1;
                y = pixel.second;
                flag = true;
                if(x < 0 || x >= h)flag = false;
                if(y < 0 || y >= w)flag = false;
                if(flag){
                    // cout << "bbbb" << endl;
                    if(seen.at(x).at(y) == -1 && !(WallHorizon.at(x-1).at(y))){
                        nextWatch_temp.push_back(make_pair(x,y));
                    }
                }

                x = pixel.first;
                y = pixel.second-1;
                flag = true;
                if(x < 0 || x >= h)flag = false;
                if(y < 0 || y >= w)flag = false;
                if(flag){
                    // cout << "cccc" << endl;
                    if(seen.at(x).at(y) == -1 && !(WallVertical.at(x).at(y))){
                        nextWatch_temp.push_back(make_pair(x,y));
                    }
                }

                x = pixel.first;
                y = pixel.second+1;
                flag = true;
                if(x < 0 || x >= h)flag = false;
                if(y < 0 || y >= w)flag = false;
                if(flag){
                    // cout << "dddd" << endl;
                    if(seen.at(x).at(y) == -1 && !(WallVertical.at(x).at(y-1))){
                        nextWatch_temp.push_back(make_pair(x,y));
                    }
                }
            }

            nextWatch = nextWatch_temp;
            counter++;

        }

        if(seen.at(h-1).at(w-1) == -1){
            cout << 0 << endl;
        }else{
            cout << seen.at(h-1).at(w-1) << endl;
        }
    }
}

Comments

[actorbug]

特定ページに載っている問題について質問する際には、そのページのURLも質問に載せてください。
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp
URLを載せないと、回答者がわざわざ問題を探さなければならないため、答えてもらえる可能性が低くなります。

Answer 1

幅優先探索の実装に誤りがあります。

Wikipediaの幅優先探索の疑似コードを見ていただくと分かりますが、「i に訪問済みの印を付ける」処理と「i を Q(キュー) に追加」する処理は、同時に行う必要があります。

しかし、ご提示のコードだと、訪問済みの印をつけているのが40行目、キューに追加するのが34, 52, 64, 76, 88行目と分かれているため、訪問済みの印がつかないままキュー上に同じ座標が何重にも登録されてしまい、キューのサイズが肥大化してメモリを使い果たしています。

ループごとのキューのサイズを表示するようにして、入力として大き目(上限30x30)の壁のない迷路を渡せば、キューのサイズが異常に増えることが分かると思います。

Comments

[Yot0916]

解決しました！ありがとうございます