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