# Untitled

unknown
plain_text
5 months ago
2.3 kB
2
Indexable
Never
```#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
```