Submission #1553766

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int H, W, K;
int MAP[1000][1000];
int x, y, vis[1000][1000];
int ans = 2147483647;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
bool check(int x, int y) {
    if (x < 0 || x > H) return 0;
    if (y < 0 || y > W) return 0;
    if (MAP[x][y]) return 0;
    return 1;
}
void DFS(int x, int y, int now) {
    if (now > K) return;
    if (vis[x][y] <= now) return;
    vis[x][y] = now;
    if (x == 1 || y == 1 || x == H || y == W) ans = min(ans, now);
    ans = min(ans, min(min((int)ceil((double)(x - 1) / K), (int)ceil((double)(y - 1) / K)), min((int)ceil((double)H - x / K), (int)ceil((double)W - y / K))) + 1);
    for (int i = 0; i < 4; i ++) {
        if (check(x + dx[i], y + dy[i])) DFS(x + dx[i], y + dy[i], now + 1);
    }
}
int main() {
    cin >> H >> W >> K;
    for (int i = 1; i <= H; i ++) {
        string s;
        cin >> s;
        for (int j = 1; j <= W; j ++) {
            if (s[j - 1] == '#') MAP[i][j] = 1;
            else {
                MAP[i][j] = 0;
                if (s[j - 1] == 'S') x = i, y = j; 
            }
        }
    }
    DFS(x, y, 0);
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result