Untitled
unknown
plain_text
a year ago
1.0 kB
1
Indexable
Never
#include <iostream> #include <fstream> #define MAX -1 using namespace std; int n; int arr[20][20]; int dR[4] = {-1, 0, 1, 0}; int dC[4] = {0, 1, 0, -1}; int dd[20][20]; int dem; int Max; void BackTrack(int i, int j) { if (i == n - 1 && j == n - 1) { Max = max(Max, dem); return; } for (int k = 0; k < 4; k++) { int x = i + dR[k]; int y = j + dC[k]; if (x >= 0 && x < n && y >= 0 && y < n && dd[x][y] == 0 && arr[x][y] != 1) { dd[x][y] = 1; if (arr[x][y] == 2) dem += 1; BackTrack(x, y); if (arr[x][y] == 2) dem -= 1; dd[x][y] = 0; } } } int main() { int t; cin >> t; for (int tc = 1; tc <= t; tc++) { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> arr[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dd[i][j] = 0; } } Max = MAX; dem = 0; dd[0][0] = 1; BackTrack(0, 0); cout << Max << endl; } }