대엉코딩

www.acmicpc.net/problem/11652

1. 풀이방법

- 정렬을 하고 , 앞에서부터 쭉 살피면서 연속된 수를 체크하고 교체 및 갱신을 수행한다.

- 값의 범위는 -2^64 ~ 2^64 까지 이므로 대략 10^19정도 이므로 카드의 값은 long long 타입을 사용해주자

- 값을 오름차순으로 정렬을 해준 후 작업을 수행

2. 주의사항

- 첫번째, 값이 달라질때만 갱신작업을 수행하므로 배열의 마지막이 왔을때는 비교작업을 한번 수행해주어야 한다.

- 두번쨰, 카드가 1개일 때를 생각해보면 maxcount=1, resultvalue=cardset[0]로 초기화 하자 

  (n이 1이면 for 문을 돌지 않으므로 ---> 100% 쯤에서 틀렸습니다가 나오면 이 문제)

- 물론 주의사항은 모두 구현 방식에 따라 다를 수 있습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n;
long long cardset[100001];
int maxcount;
long long resultvalue;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> cardset[i];
	}
	sort(cardset, cardset + n);
	maxcount = 1;
	resultvalue = cardset[0];
	int tmpcount = 1;
	for (int i = 1; i < n; i++) {
		if (cardset[i] == cardset[i - 1]) { 
			tmpcount++;
			if (i == n - 1) { //달라질때에만 값을 갱신하므로 , 마지막은 따로 계산해주어야함
				if (tmpcount > maxcount) { //같을때는 갱신하지 않는다.
					maxcount = tmpcount; resultvalue = cardset[i];
				}
			}
		}
		else {  
			if (tmpcount > maxcount) { //같을때는 갱신하지 않는다.
				maxcount = tmpcount; resultvalue = cardset[i - 1]; 
			}
			tmpcount = 1; }
	}
	cout << resultvalue;
	return 0;
}

www.acmicpc.net/problem/2792

1. 풀이방법

- 구현 문제를 많이 풀다보니 이런문제를 처음 봤을 때, 조금 당황스러웠습니다...;

- 어쨋든 최소질투심을 유발하게끔 나눠주는 방법은 1과 최대보석의 수 중에 있을 것이니까

- 이분 탐색을 통해 그것을 탐색해가면서 mid의 값이 아이들에게 조건에 맞게 나누어 줄 수 있는지 확인.

- 나누어 줄 수 있으면 더 작은 질투심을 유발할 수 있는 값이 있는지 mid보다 작은 쪽을 탐색.

- 아니라면 mid보다 큰 쪽을 탐색.

- 최소값을 출력하여 주었습니다.

2. 주의사항

- 없음.

3. 나의코드

#include<bits/stdc++.h> 
using namespace std;

long long n, m;
long long numarr[300001];
long long result = 1e18;

bool canspread(long long mid) {
    long long num = 0;
    for (int i = 0; i < m; i++) {
        num += numarr[i] / mid;
        if (numarr[i] % mid) num++;
    }
    return n >= num;
}
int main() {
    cin >> n >> m;
    long long left = 1; long long right = 0;
    for (int i = 0; i < m; i++) {
        cin >> numarr[i];
        if (right < numarr[i]) right = numarr[i];
        }
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (canspread(mid)) {
            if (result > mid) result = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    cout << result << "\n";
    return 0;
}

www.acmicpc.net/problem/2638

1. 풀이방법

- 문제를 보면 bfs를 이용해야 겠다는 생각이 들고,

- 처음에 딱 핵심이다 라고 생각되는 것은 0(빈칸) 중에서 외부공기 / 실내공기 를 나누어 주어야 한다는 것.

- 그리고 문제설정에서 외부공기는 반드시 존재하게끔 되어있습니다.

- 바로 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다" 적어도, 4자리는 외부공기라는 것

- 그래서 처음에 이 4점을 기준으로 bfs를 돌려 외부공기를 모두 2로 표시해주고 시작합니다.

- 저 같은 경우 벡터에 치즈의 자리를 모두 넣은 뒤, 이 치즈들이 사라질 때마다 이 자리들을 다시 큐에 넣어

- 이 치즈가 녹음으로써 내부공기 -> 외부공기 가 되는 것들을 체크해주었습니다.

2. 주의사항

- 이런 류의 문제에서 사라지는 c의 위치를 찾았을 때 바로 ground를 2로 바꿔버리면 그 뒤의 치즈들이 이 것에 의해

- 영향을 받을 수 있습니다. 그래서 벡터의서 check를 true로만 바꿔주고, 작업이 끝난뒤에

- check가 true인 것들을 한번에 2로 바꾸어주었습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int n, m;
//1은 치즈 , 0 은 빈칸 , 2는 실외공기
int ground[101][101];
bool visited[101][101];
int cheesecount = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
struct cheese {
	int cx, cy;
	bool check;
};
vector<pair<int, int>> sideindex;
queue<pair<int, int>> tmpq;
vector<cheese> tmpv;

void inputs() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> ground[i][j];
			if (ground[i][j] == 1) {
				cheesecount++; tmpv.push_back({ i,j,false });
			}
		}
	}
	sideindex.push_back({ 0, 0 }); sideindex.push_back({ n - 1,0 });
	sideindex.push_back({ 0,m - 1 }); sideindex.push_back({ n - 1,m - 1 });
}
bool boundcheck(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < m) return true;
	else return false;
}
void makeoutside() {
	while (!tmpq.empty()) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextx = tmpq.front().first;
			int nexty = tmpq.front().second;
			tmpq.pop();
			for (int i = 0; i < 4; i++) {
				int tx = nextx + dx[i]; int ty = nexty + dy[i];
				if (boundcheck(tx, ty) && visited[tx][ty] == false && ground[tx][ty] != 1) {
					visited[tx][ty] = true;
					tmpq.push({ tx,ty });
					ground[tx][ty] = 2;
				}
			}
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	int second = 0;		
	//실외공기 구하기
	for (int i = 0; i < 4; i++) {
		visited[sideindex[i].first][sideindex[i].second] = true;
		ground[sideindex[i].first][sideindex[i].second] = 2;
		tmpq.push(sideindex[i]);
	}
	
	makeoutside();
	while (1) {
		if (cheesecount == 0) break;
		for (int i = 0; i < tmpv.size(); i++) {
			if (tmpv[i].check == true) continue;
			int vsize = 0;
			for (int j = 0; j < 4; j++) { //4방향 탐색
				if (ground[tmpv[i].cx + dx[j]][tmpv[i].cy + dy[j]] == 2) {
					vsize++;
				}
				if (vsize >= 2) {
					cheesecount--;
					visited[tmpv[i].cx + dx[j]][tmpv[i].cy + dy[j]] = true;
					tmpv[i].check = true; //여기는 없어짐
					tmpq.push({ tmpv[i].cx + dx[j],tmpv[i].cy + dy[j] });
					break;
				}
			}
		}
		for (int i = 0; i < tmpv.size(); i++) {
			if (tmpv[i].check == true) {
				ground[tmpv[i].cx][tmpv[i].cy] = 2;
			}
		}
		makeoutside(); //없어진 치즈로 인해 실내공기에서 외부공기가 되는 녀석들 체크
		second++;
	}
	cout << second;
	return 0;
}

www.acmicpc.net/problem/17140

1. 풀이방법

- 구현 문제이고, 일단 문제를 이해를 잘해야합니다....

- 읽으면서도 이게 무슨말이지 싶고, 예시로 주어진 것들을 써보고 규칙을 정확히 이해해야 합니다.

- 읽으면서도 처음에는 숫자가 먼저 쭉 들어가고 등장횟수가 새로 배열에 들어가는 줄 알았으나 예시가 이상해서 보니

- (수, 등장횟수, 수, 등장횟수, 수 등장횟수...) 이런 순입니다

- 정렬순서를 구현했고 이차원배열로 max 범위로 잡아놓고 현재의 행의 수, 열의 수 를 관리하는 변수 두개를 두어

- 관리 하였습니다. 특별히 어려운 사항은 없었던 것 같습니다.

2. 주의사항

- 가끔 예제를 돌리다가 걸리는 사항인데, 저는 보통 n이면 0~n-1만큼을 사용합니다.

- 즉 문제에서 [r][c]를 원하면 저의 배열에서는 [r-1][c-1]의 값인거죠~!

- 여담이였고, 이 문제는 그냥 문제 자체만 잘 이해하면 되는 것 같습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int r, c, k;
int ground[101][101];
int hang = 3; //현재 행의 수
int yull = 3; //현재 열의 수
struct xx {
	int xnum;
	int totalcount;
};


void inputs() {
	cin >> r >> c >> k;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> ground[i][j];
		}
	}
}
bool compare(xx t1, xx t2) {
	if (t1.totalcount < t2.totalcount) return true;
	if (t1.totalcount == t2.totalcount) {
		if (t1.xnum < t2.xnum) return true;
		else return false;
	}
	else return false;
}

void Rcal() {
	int maxyull = 0;
	vector<int> tmpcount; //각 행의 수를 저장해두었다가 max-tmpcount[i] 만큼 0으로채우려고
	for (int i = 0; i < hang; i++) { //모든 행에 대하여
		int tmpyull = yull;
		vector<xx> xarr;
		for (int j = 0; j < tmpyull; j++) {
			if (ground[i][j] == 0) continue;
			bool c = false;
			for (int k = 0; k < xarr.size(); k++) { // 이미 있는지 확인
				if (ground[i][j] == xarr[k].xnum) {
					xarr[k].totalcount++; c = true; break;
				}
			}
			if (c == false) { //위에서 안걸러 졌으면
				xarr.push_back({ ground[i][j],1 });
			}
		}
		sort(xarr.begin(), xarr.end(), compare); //정렬
		tmpyull = xarr.size() * 2; // 새로운 열의 사이즈가 됨
		for (int j = 0; j < tmpyull; j++) {
			ground[i][j] = xarr[j / 2].xnum;
			ground[i][j + 1] = xarr[j / 2].totalcount;
			j++;
		}
		tmpcount.push_back(tmpyull);
		if (tmpyull > maxyull) { maxyull = tmpyull; }
	}
	 yull = maxyull;
	 for (int i = 0; i < tmpcount.size(); i++) { //나머지 부분 0으로 채우기
		 for (int j = yull - 1; j >= 0; j--) {
			 if (tmpcount[i] - 1 < j) {
				 ground[i][j] = 0;
			 }
			 else break;
		 }
	 }
}
void Ccal() {
	int maxhang = 0;
	vector<int> tmpcount;
	for (int i = 0; i < yull; i++) {
		int tmphang = hang;
		vector<xx> xarr;
		for (int j = 0; j < tmphang; j++) {
			if (ground[j][i] == 0) continue;
			bool c = false;
			for (int k = 0; k < xarr.size(); k++) {
				if (ground[j][i] == xarr[k].xnum) {
					xarr[k].totalcount++; c = true; break;
				}
			}
			if (c == false) {
				xarr.push_back({ ground[j][i],1 });
			}
		}
		sort(xarr.begin(), xarr.end(), compare); //정렬
		tmphang = xarr.size() * 2;
		for (int j = 0; j < tmphang; j++) {
			ground[j][i] = xarr[j / 2].xnum;
			ground[j + 1][i] = xarr[j / 2].totalcount;
			j++;
		}
		tmpcount.push_back(tmphang);
		if (tmphang > maxhang) { maxhang = tmphang; }
	}
	hang = maxhang;
	for (int i = 0; i < tmpcount.size(); i++) {
		for (int j = hang - 1; j >= 0; j--) {
			if (tmpcount[i] - 1 < j) {
				ground[j][i] = 0;
			}
			else break;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int second = 0;
	inputs();
	while (1) {
		if (ground[r-1][c-1] == k) { cout << second << "\n"; return 0; }
		if (second > 100) { cout << -1 << "\n"; return 0; }
		if (hang >= yull) {
			Rcal();
		}
		else {
			Ccal();
		}
		second++;
	}
	return 0;
}

www.acmicpc.net/problem/15900

1. 풀이방법

- 트리 구조를 이용한 DFS문제 입니다.

- 처음에 문제를 읽으면서 가장 고민이 되었던 건 리프노드는 구별이 가능한데 (간선이 1개뿐인 놈(루트제외))

- 리프노드에서 한칸 타고 부모로 올라갔을 때, 그다음 부모노드가 어떤 녀석인지를 판정을 어떻게 해야하나

- 고민을 많이하고, 결국 class로 노드를 만들어 포인터를 통해서 인접리스트 방식으로 트리를 구현해야하나 생각

- 했었는데, 너무 하기 귀찮아서 다시 문제를 읽어보았는데

- 사실 문제가 원하는 출력이 그렇게 복잡하지 않습니다. 이기냐, 지냐 만 출력하는 문제이므로

- 사실 각각의 리프노드들로 부터 루트노트(1) 까지 가는 간선의 수 (즉 높이) 들의 합이

- 홀수이냐, 아니면 짝수 이냐만 파악하면 문제의 정답을 출력할 수 있었습니다.

- 즉 ! 높이만 알면 되므로 리프노드 부터 탐색할 필요가 없이, 루트노드부터 dfs를 통해 리프노드까지 가면 됩니다!!!!

- 가장 고민하던 문제가 해결되었습니다. 그 다음 부터는 쉽습니다

- 그러므로 vector<int> tree[500001]을 통해 트리의 간선정보를 담고 

- bool visitnode[500001] 을통해 위에서 내려오는 부모노드는 방문체크를 하여 dfs탐색에서 제외 시켜줍니다.

2. 주의사항

- 리프노드는 연결된 간선이 무조건 하나!!!! 하지만 여기서 주의할 것은 간선이 하나가 될 수 있는 녀석이 하나 더

- 있습니다..>!   바로 루트노드는 간선이 하나만 연결될 수 있습니다. 그러므로 종료조건에 s!=1(루트노드)를 추가

- 해주었습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int N;
vector<int> tree[500001]; // 메모리때문에 인접행렬은 x 
bool visitnode[500001];
int totalheight = 0;
//간선이 하나만 존재하면 리프노드


void dfs(int s, int cnt) {
	if (tree[s].size() == 1 && s!=1) { //리프노드
		totalheight += cnt;
		return;
	}
	for (int i = 0; i < tree[s].size(); i++) {
		if (!visitnode[tree[s][i]]) {
			visitnode[tree[s][i]] = true;
			dfs(tree[s][i], cnt + 1);
			visitnode[tree[s][i]] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		tree[tmp1].push_back(tmp2);
		tree[tmp2].push_back(tmp1);
	}
	visitnode[1] = true;
	dfs(1, 0);
	if (totalheight % 2 == 1) cout << "Yes" << "\n";
	else { cout << "No" << "\n"; }
	
	return 0;
}

www.acmicpc.net/problem/2251

1. 풀이방법

- 물을 옮겨 담는 횟수에 제한이 없으므로 모든 경우의 수를 다 살펴보아야겠다고 생각하여

- dfs를 통해서 모든 경우의 수를 탐색했습니다.

- 종료조건을 걸어야 할까를 고민하다가 a,b,c 에 관한 3차원배열을 선언하여,

- 이미 체크를 했던 물의양 set이면 재귀를 통해 들어가지 않도록 하여 종료가 되게끔 구현하였습니다.

- 붓는 물의 양은 붓는 쪽의 물의 양과 부으려는 물통의 빈자리 중 더 적은 양 만큼을 부었습니다

2. 주의사항

- 종료조건 파악 및 구현

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int a, b, c;
bool already[201];
bool visitcheck[201][201][201];
vector<int> resultarr;

struct waterball {
	int ax, bx, cx;
};

void dfs(int ta, int tb, int tc) {
		visitcheck[ta][tb][tc] = true;
		if (ta==0) {
			if (already[tc] == false) {
				resultarr.push_back(tc);
				already[tc] = true;
			}
		}
		if (ta != 0 && tb != b) { //a에서 b로
			int tmpw = min((b - tb), (ta)); //b의 남은공간과 a의 물의 양중 작은 것
			if(visitcheck[ta-tmpw][tb+tmpw][tc]==false) dfs(ta - tmpw, tb + tmpw, tc);
		}
		if (ta != 0 && tc != c) { //a에서 c로
			int tmpw = min((c- tc), (ta)); //b의 남은공간과 a의 물의 양중 작은 것
			if (visitcheck[ta - tmpw][tb][tc+tmpw] == false) dfs(ta - tmpw, tb, tc+tmpw);
		}
		if (tb != 0 && tc != c) {//b에서 c로
			int tmpw = min((c - tc), (tb)); 
			if (visitcheck[ta][tb - tmpw][tc+tmpw] == false) dfs(ta , tb-tmpw, tc + tmpw);
		}
		if (tb != 0 && ta != a) {//b에서 a로
			int tmpw = min((a - ta), (tb)); 
			if (visitcheck[ta + tmpw][tb - tmpw][tc] == false)dfs(ta + tmpw, tb - tmpw, tc);
		}
		if (tc != 0 && ta != a) {//c에서 a로
			int tmpw = min((a - ta), (tc));
			if (visitcheck[ta + tmpw][tb][tc-tmpw] == false)dfs(ta + tmpw, tb , tc - tmpw);
		}
		if (tc != 0 && tb != b) {//c에서 b로
			int tmpw = min((b - tb), (tc));
			if (visitcheck[ta][tb + tmpw][tc-tmpw] == false)dfs(ta, tb + tmpw, tc - tmpw);
		}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> a >> b >> c;
	dfs(0, 0, c);
	sort(resultarr.begin(), resultarr.end());
	for (int i = 0; i < resultarr.size(); i++) {
		cout << resultarr[i] << " ";
	}
	return 0;
}

www.acmicpc.net/problem/1837

1. 풀이방법

- 첫번째는 소수 판별과 두번째는 longlong 범위를 넘어가는 big integer에 대한 mod연산 구현

- 이 두가지를 구현하는 문제 인데 첫번째는 에라토스테네스의 채를 이용하여 소수 set을 만들었고 (k의최대값까지)

- string으로 큰수를 받아서 (10^100 이므로) c++에서 제공하는 정수를 담는 자료형으로는 어림도 없으므로

- 그 문자열로 받은 큰 수를 int로 나누어보는 함수를 구현하였다 (나누는 수는 k보다 작으므로 int 가능)

2. 주의사항

- 제 구현에서는 소수 set을 만드는 부분과 나누어지는지 확인하는 부분이 나누어져있지만

- 짜고 나서 보니 에라토스테네스의 체를 이용하여 구해가면서 그때그때 판별을 하면 연산의 수를 줄일 수 있을

- 것 같습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;
const int maxk= 1e6+1;

bool isitprime[maxk]; //false 이면 소수
string ps;
int k;
int resulti = 0;

void makeprimeset() { //소수 판별
	isitprime[0] = true; isitprime[1] = true;
	for (int i = 2; i <= k; i++) {
		if (isitprime[i] == false) { //소수이면
			int index = i;
			int tmp = 2;
			while (index * tmp <= k) { //배수는 모두 소수가 아님
				isitprime[index * tmp] = true;
				tmp++;
			}
		}
	}
}
bool bigintdivide(int p) {
	int tmpsum = 0;
	for (int i = 0; i < ps.length(); i++) {
		tmpsum = (tmpsum * 10 + (ps[i] - '0'))%p; //앞자리수 부터
	}
	if (tmpsum == 0) return true;
	else return false;
}

bool isunderk() {
	for (int i = 2; i <k; i++) {
		if (isitprime[i] == false) {
			if (bigintdivide(i)) {
				resulti = i; return false;
			}
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> ps >> k;

	makeprimeset(); //에라토스테네스의 채
	if (isunderk()) cout << "GOOD" << "\n";
	else cout << "BAD" << " " << resulti << "\n";


	return 0;
} 

www.acmicpc.net/problem/1600

1. 풀이방법

- 약간은 어려워진 BFS인 것 같습니다.

- 체스의 나이트 처럼 이동할 수 있는 가능 횟수가 오직 K번 이므로, K번 + 나머지 횟수는 4방향탐색

- 을 통해 가야하는데 DFS로 구현을 할 경우 시간이 부족합니다.

- 그래서 BFS로 다시 짜는데, 핵심이라고 생각되는 것은 만약에 K번 중 한번을 사용하여 점프를 뛰고

- 바로 거기를 방문처리를 해버리면 4방향탐색을 통해 그쪽에 도착한 후 나중에 말 처럼 점프하는 사항을

- 고려할 수 가 없습니다.

- 그래서 평소 이용하는 visit 이차원 배열을 k의 수만큼 삼차원 배열로 만들어서

- k 중 몇번을 써서 왔는지를 확인하고 k번을 써서 i,j에 도착했을 경우 방문처리를 해줍니다.

- 만약 i,j로 왔는데 k를 한번도 사용하지 않고 왔다면 그 전에 i,j에 왔으나 k를 한번 써서 방문한 경우가 있어도

- 다시 큐로 들어가게끔 구현하였습니다.

2. 주의사항

- visit 처리

3. 나의코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int k, w, h;
int chesspan[200][200];
bool visit[200][200][31]; //k는 0~30
int horsemovex[8] = { -1,-2,-2,-1,1,2,2,1 };
int horsemovey[8] = { -2,-1,1,2,2,1,-1,-2 };
int dx[4] = { 0,0,1,-1 }; //k번을 다 소모했을 경우
int dy[4] = { 1,-1,0,0 };
int s = 0;
int mincount = 99999999;
bool fail = false;
struct xyk {
	int x, y, kn,s;
};
queue<xyk> tmpq;

void inputs() { //1은 장애물
	cin >> k >> w >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> chesspan[i][j];
		}
	}
}
bool boundcheck(int x, int y) {
	if (x >= 0 && x < h && y >= 0 && y < w) return true;
	else return false;
}
int bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			if (tmpq.empty()) { fail = true; return 0; }
			int nextx = tmpq.front().x;
			int nexty = tmpq.front().y;
			int nextk = tmpq.front().kn;
			int nexts = tmpq.front().s;
			tmpq.pop();
			if (nextx == h - 1 && nexty == w - 1) { 
				return nexts; }
			if (nextk != 0) {
				for (int i = 0; i < 8; i++) {
					int tx = nextx+ horsemovex[i]; int ty =nexty+ horsemovey[i];
					if (boundcheck(tx, ty) && visit[tx][ty][nextk-1] == false && chesspan[tx][ty] != 1) {
						tmpq.push({ tx,ty,nextk - 1,nexts +1 });
						visit[tx][ty][nextk-1] = true;
					}
				}
			}
			for (int i = 0; i < 4; i++) {
				int tx2=nextx +dx[i]; int ty2 =nexty+ dy[i];
				if (boundcheck(tx2, ty2) && visit[tx2][ty2][nextk] == false && chesspan[tx2][ty2] != 1) {
					tmpq.push({ tx2,ty2,nextk,nexts +1 });
					visit[tx2][ty2][nextk] = true;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	tmpq.push({ 0,0,k,0 });
	//출발점은 0,0 도착점은 h-1,w-1
	int r=bfs();
	if (fail == true) { cout << -1 << "\n"; }
	else cout <<r << "\n";


	return 0;
}