2010joi 予選5 計算量改善

実現したいこと

計算量を改善して
第１０回日本情報オリンピック　予選５を解きたい

前提

問題を幅優先探索で解こうとしていたがいくつかのテストケースでtleとなってしまう。

該当のソースコード

c++
1#include <iostream>
2#include <cstdio>
3#include <cstdlib>
4#include <algorithm>
5#include <cmath>
6#include <vector>
7#include <set>
8#include <map>
9#include <unordered_map>
10#include <queue>
11#include <ctime>
12#include <cassert>
13#include <complex>
14#include <string>
15#include <cstring>
16#include <chrono>
17#include <random>
18#include <bitset>
19#include <array>
20#define rep(i, v) for (int i = 0; i < (int)(v); i++)
21#define fi first 
22#define se second 
23#define pb push_back
24#define vvi vector<vector<int>> 
25#define vvl vector<vector<ll>>
26#define vi vector<int>
27#define vl vector<ll> 
28int dx[4] = { -1,0,1,0 };
29int dy[4] = { 0,1,0,-1 };
30using namespace std;
31using ll = long long;
32using P = pair<int, int>;
33using Graph = vector<vector<int>>;
34#define vb vector<bool>
35#define vvb vector<vector<bool>> 
36#define is insert
37
38
39int h, w, n;
40vector<string> st;
41vector<vector<char>> ch;
42queue<P> que;
43vvb seen;
44vvi dis;
45int ma = 0;
46void bfs(int want) {
47    while (que.size()) {
48        P p = que.front();
49        seen[p.se][p.fi] = true;
50        que.pop();
51        rep(i, 4) {
52            int sx = p.fi + dx[i];
53            int sy = p.se + dy[i];
54            if (sx >= 0 && sx < w && sy >= 0 && sy < h) {
55
56                int e = (int)ch[sy][sx] - 48;
57                //今行きたいところではない数字か空地
58                if( ((!(e == want)&&!(ch[sy][sx]=='X')) && seen[sy][sx] == false)) {
59                    que.push(P(sx, sy));
60                    dis[sy][sx] = dis[p.se][p.fi] + 1;
61                }
62                //今行きたい数字
63                if (e == want && seen[sy][sx] == false) {
64                    dis[sy][sx] = dis[p.se][p.fi] + 1;
65                    ma = max(ma, dis[sy][sx]);
66                 
67                    while (que.size())
68                        que.pop();
69                    que.push(P(sx,sy));
70                    return ;
71                }
72            }
73        }
74    }
75}
76int main() {
77
78    cin >> h >> w >> n;
79    st.resize(h);
80    rep(i, h) {
81        cin >> st[i];
82    }
83    ch.resize(h, vector<char>(w));
84    seen.resize(h, vector<bool>(w));
85    dis.resize(h, vi(w,0));
86    
87    rep(i, h) {
88        rep(j, w)
89            ch[i][j] = st[i].at(j);
90    }
91    //string 配列をcharの二次元配列にする
92    int x;
93    int y;
94    //スタート地点を探す
95    rep(i, h) {
96        rep(j, w) {
97            if (ch[i][j] == 'S') {
98                y = i;
99                x = j;
100                i = 1000000;
101                break;
102            }
103        }
104    }
105
106    //スタートから1,1~2・・・・の順で最短距離を求めていく
107    int want = 1;
108    que.push(P(x,y));
109    for (int i = 1; i <= n; i++) {
110        bfs(i);
111        que;
112        rep(i, h) {
113            rep(j, w) {
114                seen[i][j] = false;
115            }
116        }
117    }
118    cout << ma << endl;
119}
120
121
122### 試したこと
123
124bfs関数に問題があるだろうと思い、改善個所を探したがみつからなかった
125