Untitled

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int n, k, ans=0;
int A[20][20];

int delta, x, y;

void Do(int i, int j, int dir){
	delta = 0; x = 0; y = 0;

	if (dir == 0) dir = 4;
	else if (dir == 5) dir = 1;

	int q;

	//Trai sang phai
	if (dir == 1){
		q = j + 1;
		while (q >= 0 && q < n && A[i][q] != 0) {
			delta++; q++;
		}
		y = delta + 1;
	}
	//Tren xuong duoi
	else if (dir == 2) {
		q = i + 1;
		while (q >= 0 && q < n && A[q][j] != 0){
			delta++; q++;
		}
		x = delta + 1;
	}
	//Truoc ra sau
	else if (dir == 3) {
		q = j - 1;
		while (q >= 0 && q < n && A[i][q] != 0) {
			delta++; q--;
		}
		y = -(delta + 1);
	}	
	//Duoi len tren, dir == 4
	else {
		q = i - 1;
		while (q >= 0 && q < n && A[q][j] != 0) {
			delta++; q--;
		}
		x = -(delta + 1);
	}
}

void Try(int step, int num, int i, int j, int dir){
	//Stop
	if (step > k || i < 0 || i >= n || j < 0 || j >= n) return;
	//Update
	if (ans < num) ans = num; 
	
	if (dir == 0) dir = 4;
	else if (dir == 5) dir = 1;
	
	//Check candidates
	for (int turn = -1; turn <= 1; turn++){
		Do (i, j, dir + turn);
		Try (step + 1, num + delta, i + x, j + y, dir + turn);
	}
}

int main(){

	freopen("input.txt", "r", stdin);
	int T, tc;
	cin >> T;
	for (tc = 1; tc <= T; tc++){
		cin >> n >> k;
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				cin >> A[i][j];
			}
		}
		//Tim vi tri dau tien de dat Domino
		int ystart;
		bool find = false;
		for (int j = 0; j < n; j++){
			if (A[0][j] == 0){
				ystart = j;
				find = true;
				break;
			};
		}
		//Thu dat Domino
		if (find) Try (0,ystart,0,ystart,1); 
		else ans = n; 

		cout <<"#" << tc << " " << ans << endl;
	}

	return 0;
}

// Input:
// 3
// 8 5
// 1 1 0 1 1 1 0 0
// 0 0 0 0 0 0 1 0
// 0 0 1 0 0 0 1 0
// 0 0 1 0 0 0 1 0
// 0 0 0 1 1 1 0 0
// 0 0 1 0 0 0 1 0
// 0 0 1 0 0 0 0 0
// 0 0 0 1 1 1 0 0
// 7 5
// 1 1 1 1 1 1 0
// 1 1 1 1 1 1 1
// 1 1 1 1 1 1 1
// 0 1 1 0 1 1 0
// 1 1 1 1 1 1 1
// 1 1 1 1 1 1 1
// 0 1 1 0 1 1 0
// 8 5
// 1 1 0 1 1 1 0 0
// 0 0 0 0 0 0 1 0
// 0 0 1 1 0 0 1 0
// 0 1 0 0 0 0 1 0
// 0 0 1 1 1 1 0 0
// 0 1 0 0 0 0 1 0
// 0 1 0 0 0 0 0 0
// 0 0 1 1 1 1 0 0
// Output:
// 16
// 16
// 18