Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
3
Indexable
Never
#include<iostream>

using namespace std;

enum parity {EVEN = 0, ODD = 1};

int visited1[20][20];
int N; // number rows
int M; // number colums
int map[20][20]; // map mat ong

void reset1()
{
	for(int i =0; i< 20; i++)
		for(int j =0; j< 20; j++)
		{
			visited1[i][j] = false;
		}
}

int dxEven[6] = {0,-1,0,1,1,1};
int dyEven[6] = {-1,0,1,1,0,-1};

int dxOdd[6] = {-1,-1,-1,0,1,0};
int dyOdd[6] = {-1,0,1,1,0,-1};

bool visited[20][20];

parity isParity(int i)
{
	if(i % 2 == 0)
		return ODD; // vi tri le
	return EVEN;
}

bool isSafe(int x, int y)
{
	if(x >= 0 && x < N && y >= 0 && y < M)
		return true;
	return false;
}

int maxSum;

void backTrack(int k,int x, int y, int sum)
{
	if(k == 3)
	{
		
		if(sum > maxSum) 
		{
			reset1();
			for(int i =0; i< 20; i++)
			for(int j =0; j< 20; j++)
		{
			visited1[i][j] = visited[i][j];
		}
			maxSum = sum;
		}
		return;
	}
	for(int i = 0; i < 6; i++)
	{
		int xx, yy;
		if(isParity(y) == EVEN)
		{
			xx = x + dxEven[i];
			yy = y + dyEven[i];
		}
		else if(isParity(y) == ODD)
		{
			xx = x + dxOdd[i];
			yy = y + dyOdd[i];
		}
		if(isSafe(xx,yy) && !visited[xx][yy])
		{
			visited[xx][yy] = true;
			backTrack(k+1,xx,yy, sum + map[xx][yy]);
			backTrack(k+1,x,y, sum + map[xx][yy]);
			visited[xx][yy] = false;
		}
	}
}

void input()
{
	cin>>M>>N;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			cin>>map[i][j];
		}
	}
}

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

int main()
{
	freopen("Text.txt","r",stdin);

	int T;
	cin>>T;
	for(int tc = 1; tc <= T; tc++)
	{
		input(); // nhap input N, M, ma tran value mat ong
		reset();
		maxSum = 0;
		for(int i = 0; i < N; i++)
			for(int j = 0; j< M; j++)
			{
				visited[i][j] = true;
				backTrack(0,i,j,map[i][j]);
				reset();
			}
			int ans = maxSum;
			cout<<"Case #"<<tc<<endl;
			cout<<ans<<endl;
	}

	return 0;
}