AGC014C: Closed Rooms

https://agc014.contest.atcoder.jp/tasks/agc014_c

結局1回目は開いているところをK回移動、2回目以降は壁を壊しながらK回移動と言い換えられます。
なので2回目以降は4方向のうち一番近い場外へ直線で行くのが最適です。

変数がsx,x,nxと結構出てきてしまったんですけど、xに関する変数がもうひとつあったらバグらせる原因になりますね…考えどころです。
あとcontinueはなるべく使わないようにしました。カッコがないと逆にわかりにくいので。

int N, M, K;
bool vsd[1010][1010];
char S[1010][1010];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void solve() {
	cin >> N >> M >> K;
	int sx, sy;
	rep(i, 0, N) {
		rep(j, 0, M) {
			cin >> S[i][j];
			if(S[i][j] == 'S') {
				sx = i; sy = j;
			}
		}
	}
	queue<pi> que;
	vsd[sx][sy] = true;
	que.push(pi(sx, sy));
	rep(q, 0, K) {
		int qs = sz(que);
		while(qs--) {
			pi p = que.front(); que.pop();
			int x = p.fst, y = p.sec;
			rep(i, 0, 4) {
				int nx = x + dx[i], ny = y + dy[i];
				if(0 <= nx && nx < N && 0 <= ny && ny < M) {
					if(S[nx][ny] != '#' && !vsd[nx][ny]) {
						vsd[nx][ny] = true;
						que.push(pi(nx, ny));
					}
				}
			}
		}
	}
	int ans = inf;
	rep(i, 0, N) {
		rep(j, 0, M) {
			if(vsd[i][j]) {
				MIN(ans, 1 + (min(min(i, j), min(N - 1 - i, M - 1 - j)) + K - 1) / K);
			}
		}
	}
	cout << ans << "\n";
}