
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int M = 1e3;
char mmp[M][M] , s[M][M];
int h , w , k , step[M][M] , dr[4][2] = {1 , 0 , -1 , 0 , 0 , 1 , 0 , -1};
struct TnT {
    int x , y , step , flag;
};
bool vis[M][M];
void bfs(TnT sta) {
    memset(step , 0 , sizeof(step));
    step[sta.x][sta.y] = 1;
    memset(vis , false , sizeof(vis));
    vis[sta.x][sta.y] = true;
    queue<TnT>q;
    q.push(sta);
    while(!q.empty()) {
        TnT gg = q.front();
        q.pop();
        for(int i = 0 ; i < 4 ; i++) {
            TnT gl = gg;
            gl.x += dr[i][0];
            gl.y += dr[i][1];
            if(gl.x >= 0 && gl.x < h && gl.y >= 0 && gl.y < w && mmp[gl.x][gl.y] != '#' && !vis[gl.x][gl.y]) {
                gl.step++;
                step[gl.x][gl.y] = gl.step;
                vis[gl.x][gl.y] = true;
                q.push(gl);
            }
        }
    }
}
int main() {
    scanf("%d%d%d" , &h , &w , &k);
    for(int i = 0 ; i < h ; i++) {
        scanf("%s" , mmp[i]);
    }
    TnT sta;
    for(int i = 0 ; i < h ; i++) {
        for(int j = 0 ; j < w ; j++) {
            if(mmp[i][j] == 'S') {
                sta.x = i , sta.y = j;
                break;
            }
        }
    }
    sta.step = 0 , sta.flag = k;
    bfs(sta);
    int ans = 1000000000;
    for(int i = 0 ; i < h ; i++) {
        for(int j = 0 ; j < w ; j++) {
            if(step[i][j] != 0) {
                if(i == 0 || i == h - 1 || j == 0 || j == w - 1) {
                    int gg = step[i][j];
                    if(gg % k == 0) {
                        ans = min(ans , gg / k);
                    }
                    else {
                        ans = min(ans , gg / k + 1);
                    }
                }
                else {
                    int gg = step[i][j] , gl = 0;
                    if(gg % k == 0) {
                        gl = gg / k;
                    }
                    else {
                        gl = gg / k + 1;
                    }
                    gg = i;
                    if(gg % k == 0) {
                        ans = min(ans , gl + gg / k);
                    }
                    else {
                        ans = min(ans , gl + gg / k + 1);
                    }
                    gg = j;
                    if(gg % k == 0) {
                        ans = min(ans , gl + gg / k);
                    }
                    else {
                        ans = min(ans , gl + gg / k + 1);
                    }
                    gg = h - 1 - i;
                    if(gg % k == 0) {
                        ans = min(ans , gl + gg / k);
                    }
                    else {
                        ans = min(ans , gl + gg / k + 1);
                    }
                    gg = w - 1 - j;
                    if(gg % k == 0) {
                        ans = min(ans , gl + gg / k);
                    }
                    else {
                        ans = min(ans , gl + gg / k + 1);
                    }
                }
            }
        }
    }
    printf("%d\n" , ans);
    return 0;
}