Submission #3610660

---

Source Code Expand

#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;
typedef pair<int,int> pii;
typedef vector<int> vi;


const int MAX_H = 800, MAX_W = 800;
int h,w,k;
char grid[MAX_H][MAX_W];
const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};
bool kr[MAX_H][MAX_W] = {};

bool is_edge(int i, int j)
{
  return i == 0 || i == h-1 || j == 0 || j == w-1;
}

int ceil(int a, int b)
{
  return a / b + (a % b != 0 ? 1 : 0);
}

int main()
{
  cin >> h >> w >> k;
  int si,sj;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      cin >> grid[i][j];
      if (grid[i][j] == 'S') {
        si = i;
        sj = j;
      }
    }
  }

  queue<pair<pii,int> > q({{{si,sj},k}});
  kr[si][sj] = true;
  while (!q.empty()) {
    auto p = q.front(); q.pop();
    if (p.second == 0) break;
    for (int i = 0; i < 4; i++) {
      int new_x = p.first.first + dx[i];
      int new_y = p.first.second + dy[i];
      if (!kr[new_x][new_y] && grid[new_x][new_y] != '#') {
        if (is_edge(new_x, new_y)) {
          cout << 1 << endl;
          return 0;
        }
        q.push({{new_x,new_y},p.second-1});
        kr[new_x][new_y] = true;
      }
    }
  }

  int c = INT_MAX;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (kr[i][j]) {
        c = min({c, ceil(i,k), ceil(h-1-i,k), ceil(j,k), ceil(w-1-j,k)});
      }
    }
  }
  cout << c+1 << endl;

  return 0;
}

Submission Info

Judge Result