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
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e6+7, INF = 400000;
vector<int> G[maxn];
int parent_l[maxn], parent_r[maxn], visited[maxn], moves[maxn], result;
pair<int, int> decode[maxn];
map<pair<int, int>, int> code;
vector<int> input[2005];
queue<int> q;

void bfs(int start, int k){
	visited[start] = 1;
	q.push(start);
	while(!q.empty()){
		int a = q.front();
		//cout<<moves[a]<<" "<<input[decode[a].first][decode[a].second]<<" "<<decode[a].first<<" "<<decode[a].second<<endl;
		q.pop();
		pair<int, int> temp = decode[a];
		if(moves[a] <=k && input[temp.first][temp.second]==1){
			result = 1;
			return ;
		}
		if(moves[a] <= k && result>input[temp.first][temp.second])
			result = input[temp.first][temp.second];
		for(int i=0; i<G[a].size(); i++){
			if(visited[G[a][i]]!=1){
				if(min(parent_r[G[a][i]], parent_l[G[a][i]]) == 0)
					moves[G[a][i]] = max(moves[parent_r[G[a][i]]], moves[parent_l[G[a][i]]]) +1;
				else{
					moves[G[a][i]] = max(moves[parent_l[G[a][i]]], moves[parent_r[G[a][i]]]) + min(moves[parent_l[G[a][i]]], moves[parent_r[G[a][i]]]) + 1;
					if(moves[parent_l[G[a][i]]]<moves[parent_r[G[a][i]]])
						moves[G[a][i]]-=max(moves[parent_r[parent_l[G[a][i]]]], moves[parent_l[parent_l[G[a][i]]]]);
					else
						moves[G[a][i]]-=max(moves[parent_r[parent_r[G[a][i]]]], moves[parent_l[parent_r[G[a][i]]]]);
				}
				visited[G[a][i]]=1;
				if(moves[G[a][i]]<=k)
					q.push(G[a][i]);
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	int n, k, counter=0;
	cin>>n>>k;
	vector<int>temp1, temp2;
	for(int i=0; i<n; i++)
		for(int j=0; j<=i; j++){
			int a;
			cin>>a;
			input[i].push_back(a);
			decode[counter] = make_pair(i, j);
			code[make_pair(i,j)] = counter;
			int v = counter, father_l, father_r;
			if(i>0){
				if(j-1>=0){
					father_l = code[make_pair(i-1, j-1)];
					G[father_l].push_back(v);
					parent_l[v] = father_l;
					if(j<i){
						father_r = code[make_pair(i-1, j)];
						parent_r[v] = father_r;
						G[father_r].push_back(v);
					}
				}
				else
				if(j<i){
					father_r = code[make_pair(i-1, j)];
					parent_r[v] = father_r;
					G[father_r].push_back(v);
					if(j-1>=0){
						father_l = code[make_pair(i-1, j-1)];
						parent_l[v] = father_l;
						G[father_l].push_back(v);
					}
				}
			}
			counter++;
		}
	moves[0] = 1;
	result = INF;
	bfs(0, k);
	cout<<result<<endl;
}