Submission #1794247

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int u[100001];
int d1[] = {1, -1, 0, 0};
int d2[] = {0, 0, 1, -1};
int d[1001][1001];
queue <pair <int, int> > q;
char a[1001][1001];

 main () {
	ios_base::sync_with_stdio (0);
	cin.tie (0);
	int n, m, k;
	cin >> n >> m >> k;
	int starti, startj;
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= m;j ++) {
			cin >> a[i][j];
			if (a[i][j] == 'S') {
				starti = i;
				startj = j;
			}
		}
	}
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= m;j ++) {
			d[i][j] = 1e9 + 7;
		}
	}        
	d[starti][startj] = 0;
	q.push (make_pair (starti, startj)); 
	while (q.size ()) {
		int r = q.front ().first;
		int c = q.front ().second;
		q.pop ();
		for (int i = 0;i <= 3;i ++) {
			int x = d1[i];
			int y = d2[i];
			if (r + x < 1 || r + x > n || c + y  < 1 || c + y > m) continue;
			if (d[r][c] + 1 < d[r + x][y + c] && a[r + x][y + c] == '.') {
				q.push (make_pair (r + x, c + y));	
				d[r + x][y + c] = d[r][c] + 1;
			}
		}
	}
	int ans = 1e9 + 7;
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= m;j ++) {
			if (d[i][j] == 1e9 + 7) continue;
			int mn = min ({n - i, i - 1, m - j, j - 1});
			int jkl = mn / k;
			if (mn % k) jkl ++;
			ans = min (ans, jkl + 1);
		}
	}
	cout << ans;
	return 0;
}

Submission Info

Judge Result