

[ATC001 A
深さ優先探索](https://atcoder.jp/contests/atc001/tasks/dfs_a)をC++で以下のように実装しましたが、88個中12個TLE、2個MLEになってしまいました。  
再帰を用いています。  
goalの座標も引数に渡して、v=goalとなったらreturnするというのも試しましたが、ダメでした。  
どう直せば良いでしょうか。

[code]

    #include <bits/stdc++.h>
    using namespace std;
    
    vector<vector<int>> dxdy = {{1,0},{-1,0},{0,1},{0,-1}};
    
    void dfs(vector<string> c, int h, int w, vector<int> v, vector<vector<bool>> &seen) {
        seen[v[0]][v[1]] = true;
    
        for (int i=0; i<4; i++){
            int nxtX=v[0]+dxdy[i][0], nxtY=v[1]+dxdy[i][1];
    
            if (nxtX<0 || nxtY<0 || nxtX>=h || nxtY>=w) continue;
            if (seen[nxtX][nxtY]) continue;
            if (c[nxtX][nxtY]=='#') continue;
            dfs(c, h, w, {nxtX,nxtY}, seen);
        }
    }
    
    int main() {
        int h, w;
        cin >> h >> w;
        vector<string> c(h);
        vector<int> start(2), goal(2);
    
        for (int i=0; i<h; i++) {
            cin >> c[i];
            for (int j=0; j<w; j++){
                if (c[i][j]=='s') start = {i,j};
                else if (c[i][j]=='g') goal = {i,j};
            }
        }
        vector<vector<bool>> seen(h, vector<int>(w, false));
    
        dfs(c, h, w, start, seen);
    
        if (seen[goal[0]][goal[1]]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    
[/code]


CC BY-SA 4.0
2022-07-29T06:47:06.953
90269
2022-07-30T03:02:05.087
2022-07-29T06:52:21.130
53750
53750
question
c++ アルゴリズム
Atcoder ATC001 A 深さ優先探索をC++で再帰を用いて実装したがTLEになってしまう


`dfs`で`c`を値渡しているために、関数の呼び出しのたびに`c`の内容がコピーされていることが原因だと考えられます。`seen`のように参照渡しに書き換えてみてください。

計算量について考えてみると、`O(n^2)`個の区画を訪れるごとにコピーに`O(n^2)`の時間をかけることになるので、全体としては`O(n^4)`の時間がかかることになり、実行時間制限に間に合いません。特に家を端点の一方とするような長いパスを含む入力の場合に、再帰が深くなり`c`のコピーでメモリを使い切ってしまうことでMLEが発生していると考えられます.


CC BY-SA 4.0
2022-07-30T03:02:05.087
90278
2022-07-30T03:02:05.087
13199
90269
answer