BOJ16933

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXN 1000
int N, M, K;
bool visited[MAXN][MAXN][11][2];
int map[MAXN][MAXN];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
struct node {
	int x;
	int y;
	int cnt;
	int state;
};
int bfs() {
	queue<node> q;
	q.push({ 0,0,0,1 });
	visited[0][0][0][1] = true;
	int ans = 0;
	while (!q.empty()) {
		int q_size = q.size();

		while (q_size--) {
			int x = q.front().x;
			int y = q.front().y;
			int cnt = q.front().cnt;
			int state = q.front().state;
			if (x == N - 1 && y == M - 1) return ans + 1;
			q.pop();
			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				if (state == 1) {
					if (map[nx][ny] == 0) {
						if (visited[nx][ny][cnt][1-state]) continue;
						visited[nx][ny][cnt][1-state] = true;
						q.push({ nx,ny,cnt,1 - state });
					}
					else {
						if (cnt < K && !visited[nx][ny][cnt+1][1-state]) {
							visited[nx][ny][cnt + 1][1-state] = true;
							q.push({ nx,ny,cnt + 1,1 - state });
						}
					}
				}
				else {
					if (map[nx][ny] == 0) {
						if (visited[nx][ny][cnt][1-state]) continue;
						visited[nx][ny][cnt][1-state] = true;
						q.push({ nx,ny,cnt,1 - state });
					}
					else {
						if (visited[x][y][cnt][1 - state]) continue;
						visited[x][y][cnt][1 - state] = true;
						q.push({ x,y,cnt,1 - state });
					}
				}
				
			}
		}
		ans++;
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	scanf("%d%d%d", &N, &M, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	
	cout << bfs() << "\n";
	
	
	return 0;
}