Submission #70141773

---

Source Code Expand

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

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int h, w;
  cin >> h >> w;

  vector<string> s(h);
  for (int i=0; i<h; i++) {
    cin >> s.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  int result = -1;

  //////////////////// 処理 ////////////////////

  // 高橋君の位置を探す
  int ti, tj;
  for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {
      if (s.at(i).at(j)=='T') {
        ti = i;
        tj = j;
      }
    }
  }

  // 6次元BFS用のdeque
  // そこまでの移動回数、ゴミを上に最大で何マス動かしたか、同じく下、左、右、
  // 高橋君の位置がもともとのゴミ配置のどこ相当なのかのiとj
  deque<tuple<int,int,int,int,int,int,int>> que;
  que.emplace_back(0,0,0,0,0,ti,tj);

  set<tuple<int,int,int,int,int,int>> visited;

  // BFSする
  while (!que.empty()) {

    // とりあえず取り出す
    auto [time,u,d,l,r,i,j] = que.front();
    que.pop_front();

    // そのルートの上下左右の移動量新記録だったら更新しておく
    u = max(u,i-ti);
    d = max(d,ti-i);
    l = max(l,j-tj);
    r = max(r,tj-j);

    // 訪問済だったらスキップ、そうじゃなければ訪問済に記録
    if (visited.contains({u,d,l,r,i,j})) continue;
    visited.emplace(u,d,l,r,i,j);

    // 最大移動量から「ここにゴミがあったらまだ残ってる」範囲を判断し、その範囲を全探索
    bool flag = true;
    for (int pi=u; pi<h-d; pi++) {
      for (int pj=l; pj<w-r; pj++) {
        if (s.at(pi).at(pj)=='#') {
          flag = false;
          break;
        }
      }
      if (!flag) break;
    }

    // 結果ゴミがなかったら掃除完了で、BFSなので初めて見つけたものをそのまま答えにして終了でいい
    if (flag) {
      result = time;
      break;
    }

    // 上下左右、ゴミ消し完了マスか、もともとゴミがないマスなら移動してよし
    vector<pair<int,int>> vec = {{-1,0},{1,0},{0,-1},{0,1}};
    for (auto [di,dj] : vec) {
      if (i+di<u||i+di>=h-d||j+dj<l||j+dj>=w-r||s.at(i+di).at(j+dj)!='#') {
        que.emplace_back(time+1,u,d,l,r,i+di,j+dj);
      }
    }
    
  }


  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:54:17: warning: ‘tj’ may be used uninitialized [-Wmaybe-uninitialized]
   54 |     r = max(r,tj-j);
      |               ~~^~
Main.cpp:25:11: note: ‘tj’ was declared here
   25 |   int ti, tj;
      |           ^~
Main.cpp:52:17: warning: ‘ti’ may be used uninitialized [-Wmaybe-uninitialized]
   52 |     d = max(d,ti-i);
      |               ~~^~
Main.cpp:25:7: note: ‘ti’ was declared here
   25 |   int ti, tj;
      |       ^~

Judge Result