AGC014 C - Closed Rooms

問題のリンク

C - Closed Rooms

考察

操作は、
1. 最大Kマス進む
2. 最大K個'#' を'.' に変える

ゴールするのは操作1 をした直後であるので、1→2 という操作を考える代わりに2→1 と考えたほうが見通しが良さそう。

2→1 という操作を考えると、1 で進むKマスを2 で進めるように変えることができるので、2→1 という操作は「好きなように隣接するマスにK回移動する」、という操作とみなして良い。

マス(i, j) からゴールに向かう最善手は、直線距離で一番近いところにまっすぐ向かう、である。

2→1 という操作とするので、最初の1 でいけるマスを全てスタートマスとして直線距離で端に向かわせれば良い。

以下実装

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  int h,w,k;cin >> h >> w >> k;
  vector<vector<char>> a(h, vector<char>(w));
  int sx, sy;
  rep(i,h) rep(j,w) {
    cin >> a[i][j];
    if(a[i][j] == 'S') {
      sx = i; sy = j;
    }
  }

  vector<int> dx = {1, 0, -1, 0};
  vector<int> dy = {0, 1, 0, -1};

  const int inf = 1e+9;
  vector<vector<int>> d(h, vector<int>(w, inf));
  d[sx][sy] = 0;
  using pi = pair<int,int>;
  queue<pi> q;
  q.push({sx, sy});
  while( !q.empty() ) {
    pi p = q.front(); q.pop();
    int x = p.first, y = p.second;
    rep(i,4) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(0 <= nx && nx < h && 0 <= ny && ny < w) {
    if(a[nx][ny] == '#' || d[nx][ny] != inf) continue;
    d[nx][ny] = d[x][y] + 1;
    q.push({nx, ny});
      }
    }
  }
  int res = 1e+9;

  auto Ceil = [](int a, int b)-> int{
        if(a%b == 0) return a/b;
        else return (a+b-a%b)/b;
          };
  
  rep(i,h) rep(j,w) {
    if(d[i][j] <= k) {
      int dis = min({i, h-i-1, j, w-j-1});
      chmin(res, Ceil(dis,k) + 1);
    }
  }
  cout << res << "\n";
  
  return 0;
}