〜九州大学プログラミングコンテスト2018〜 C - Ito Campus

問題

C - Ito Campus

感想

はじめてBPS（幅優先探索）を実装してみた。 割とTLEになる条件が厳しかったので厳格に実装する必要があるんだなあと思いました。 BPSの中で、四方へ進む際に一回一回その方向でいいのか考える必要がない（つまり、その四方へ進む方向が最短経路となっている）ということはすごいと思いました（コードでいうとdp[pi + vi[i]][qi + vj[i]] = dp[pi][qi] + 1;に対応しています）。

考え

以下の2回に分けて、BPSを使います。

1. イノシシのいる位置からStartして、新しい#の範囲を作っていく
2. SからBPSしてGまでたどっていく

Accepted Program

可読性がない...

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long

ll abs (ll x, ll y) {
  if (x - y) {
    return x - y;  
  }  
  return y - x;
}

int main () {
  ll h, w, x;
  cin >> h >> w >> x;
  char s[h][w];
  ll dp[h][w];
  ll xa[h][w];
  vector<int> ii;
  vector<int> jj;
  int si = 0;
  int sj = 0;
  for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      s[i][j] = -1;
      dp[i][j] = -1;
      xa[i][j] = -1;
      cin >> s[i][j];
      if (s[i][j] == '@') {
        ii.push_back(i);
        jj.push_back(j);
        xa[i][j] = x;  
      }  
      if (s[i][j] == 'S') {
        si = i;
        sj = j;  
      }
    }  
  }
  ll vi[4] = {0, 0, 1, -1};
  ll vj[4] = {1, -1, 0, 0};
  for (ll i = 0; i < ii.size(); i++) {
    queue<ll> li;
    queue<ll> lj;
    li.push(ii[i]);
    lj.push(jj[i]);
    while (!li.empty()) {
      ll xi, xj;
      xi = li.front();
      xj = lj.front();
      li.pop();
      lj.pop();
      
      for (int a = 0; a < 4; a++) {
          
        if (xi + vi[a] > 0 && xi + vi[a] < h && xj + vj[a] > 0 && xj + vj[a] < w) {
          if (s[xi + vi[a]][xj + vj[a]] == '@') {
            // 何もしない.  
          }
          if (s[xi + vi[a]][xj + vj[a]] == '#') {
            // 同上  
          }
          if (s[xi + vi[a]][xj + vj[a]] == '.'
            ||s[xi + vi[a]][xj + vj[a]] == 'G'
            ||s[xi + vi[a]][xj + vj[a]] == 'S')
          {
            ll sub = xa[xi][xj] - 1;
            if (xa[xi + vi[a]][xj + vj[a]] < 0) {
              xa[xi + vi[a]][xj + vj[a]] = xa[xi][xj] - 1;
              if (sub > 0) {
                li.push(xi + vi[a]);
                lj.push(xj + vj[a]);
              }
            }
          }
        }    
      }  
    }
  }
  // まさかのここも探索だったとは.....

  
  ll gi, gj;
  gi = 0;
  gj = 0;
  bool ok = false;
  for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      if (xa[i][j] >= 0) {
        if (s[i][j] == 'G') {
          cout << -1 << endl;
          return 0;   
        }
        s[i][j] = '#';
      }
      if (s[i][j] == 'G') {
        gi = i;
        gj = j;  
      }
    } 
  }
  // 幅優先探索で求める。
  dp[si][sj] = 0;
  queue<ll> P;
  queue<ll> Q;
  P.push(si);
  Q.push(sj);
  
  while (!P.empty()) {
    ll pi = P.front();
    ll qi = Q.front();

    if (pi == gi && qi == gj) {
      cout << dp[pi][qi] << endl;
      return 0;  
    }
    for (int i = 0; i < 4; i++) {
      if (pi + vi[i] > 0 && pi + vi[i] < h && qi + vj[i] > 0 && qi + vj[i] < w) {
        if (s[pi + vi[i]][qi + vj[i]] != '#' && s[pi + vi[i]][qi+vj[i]] != '@') {
          if (dp[pi + vi[i]][qi + vj[i]] < 0) {        
            P.push(pi + vi[i]);
            Q.push(qi + vj[i]);    
            dp[pi + vi[i]][qi + vj[i]] = dp[pi][qi] + 1;
          }
        }  
      }       
    }
    P.pop();
    Q.pop();
  }
  cout << dp[gi][gj] << endl;
  /*for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      cout << dp[i][j] << " " ;  
    }  
    cout << endl;
  }
  */
}