Untitled

#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;
	}
}