質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.36%
C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

Q&A

解決済

1回答

236閲覧

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

Yot0916

総合スコア1

C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

0グッド

0クリップ

投稿2024/09/14 06:35

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; } } }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

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

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

投稿2024/09/14 09:44

編集2024/09/14 20:37
actorbug

総合スコア2420

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Yot0916

2024/09/14 14:33

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.36%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問