Untitled

Price Tag
Cho một hình vuông NxN ô nhỏ (5 ≤ N ≤ 9), mỗi ô chứa 1 số từ 0 – 9.
Nhiệm vụ cần làm là cắt hình vuông lớn thành (N+1) hình có kích thước 1x(N-1). Mỗi hình kích thước 1x(N-1) bao gồm (N-1) chữ số và tạo thành 1 số nguyên (N-1) chữ số (đọc từ trái qua phải hoặc từ trên xuống dưới tùy theo phương án cắt). 

Sau khi có được các miếng cắt, tính tổng các số thu được (chỉ tính các số có N-1 chữ số, ô còn sót lại sẽ không được tính vào tổng). 
Hãy tìm ra phương án cắt có tổng thu được lớn nhất.

Input
Input sẽ chứa một hoặc nhiều test cases 
Dòng đầu là số lượng test case T (T ≤ 50)
Dòng đầu tiên của mỗi test cases là kích thước hình vuông N (5 ≤ N ≤ 9)
N dòng tiếp theo lần lượt là giá trị trong các ô nhỏ của hình vuông lớn. 
 
Output
Với mỗi test case, in ra tổng số lớn nhất thu được. 

Sample
Input
6
3 4 5 6 8 6
3 5 6 7 7 8
3 3 3 3 3 5
1 2 5 6 4 2
3 3 5 5 5 7
8 5 3 6 9 9
6
3 4 5 6 8 6
3 5 6 7 7 8
3 3 3 3 3 5
1 2 5 6 4 2
3 3 5 5 5 7
8 5 3 6 9 9

Output
#1 35000
#2 72000


#include <iostream>
using namespace std;

int arr[10][10];
bool visited[10][10];

void reset(int a[10][10])
{
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			a[i][j] = 0;
			visited[i][j] = false;
		}
	}
}

int N;

bool check1(int s, int k, int y)
{
	if (k >= N || k < 0)
	{
		return false;
	}
	for (int i = s; i <= k; i++)
	{
		if (visited[i][y] == true)
		{
			return false;
		}
	}
	return true;
}

bool check2(int s, int k, int x)
{
	if (k >= N || k < 0)
	{
		return false;
	}
	for (int j = s; j <= k; j++)
	{
		if (visited[x][j] == true)
		{
			return false;
		}
	}
	return true;
}

long long danhdau1(int s, int k, int y)
{
	long long sum = 0;
	for (int i = s; i <= k; i++)
	{
		if (visited[i][y] == false)
		{
			visited[i][y] = true;
			sum = sum * 10 + arr[i][y];
		}
		else
			visited[i][y] = false;
	}
	return sum;
}

long long danhdau2(int s, int k, int x)
{
	int sum = 0;
	for (int j = s; j <= k; j++)
	{
		if (visited[x][j] == false)
		{
			visited[x][j] = true;
			sum = sum * 10 + arr[x][j];
		}
		else
			visited[x][j] = false;
	}
	return sum;
}


void xep(long long& max, long long sum, int k, int s)
{
	int x = k / N;
	int y = k % N;
	if (s == N + 1)
	{
		if (max < sum)
		{
			max = sum;
		}
		return;
	}
	if (visited[x][y] == true)
	{
		xep(max, sum, k + 1, s);
	}
	else
	{
		// co hai cach cach xoay ngang doc
		for (int i = 0; i <= 1; i++)
		{
			if (i == 0)
			{
				// chon quay theo huong ngang
				if (check2(y, y + N - 2, x))
				{
					long long t = danhdau2(y, y + N - 2, x);
					xep(max, sum + t, k, s + 1);
					danhdau2(y, y + N - 2, x);
				}
			}
			else
			{
				// chon quay theo huong doc
				if (check1(x, x + N - 2, y))
				{
					long long t = danhdau1(x, x + N - 2, y);
					xep(max, sum + t, k, s + 1);
					danhdau1(x, x + N - 2, y);
				}
			}
		}
	}
}

int main()
{
	int testcase;
	cin >> testcase;
	for (int tc = 1; tc <= testcase; tc++)
	{
		reset(arr);
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> arr[i][j];
			}
		}
		long long max = 0;
		visited[0][0] = true;
		xep(max, 0, 0, 0);
		visited[0][0] = false;
		visited[0][N - 1] = true;
		xep(max, 0, 0, 0);
		visited[0][N - 1] = false;
		visited[N - 1][0] = true;
		xep(max, 0, 0, 0);
		visited[N - 1][0] = false;
		visited[N - 1][N - 1] = true;
		xep(max, 0, 0, 0);
		visited[N - 1][N - 1] = false;
		cout << "#" << tc << " " << max << endl;

	}
}