Untitled

mail@pastecode.io avatar
unknown
plain_text
16 days ago
1.8 kB
1
Indexable
Never
#include <iostream>
using namespace std;
typedef long long ll;

const int CAPACITY = 1e6, inf = 1e7, MAX = 101, CANT = -1;

ll n, m, res;
ll board[MAX][MAX];
int visited[MAX][MAX];

void input(){
	cin >> m >> n;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			cin >> board[i][j];
		}
	}
}

void resetData(){
	res = 0;
	for (int i=0; i<MAX; i++){
		for (int j=1; j<MAX; j++){
			visited[i][j] = 0;
		}
	}
}

//cot chan cot le
int dirR_chan[6] = { 1, -1,  1,  1,  0, 0};
int dirC_chan[6] = { 0,  0, -1,  1, -1, 1};

int dirR_le[6]   = { 1, -1, -1, -1,  0, 0};
int dirC_le[6]   = { 0,  0, -1,  1, -1, 1};

bool checkInBoard(int r, int c){
	return r>0 && c>0 && r<=n && c<=m;
}

void Try(int r, int c, int cnt, int sum){
	if (cnt >= 4){
		res = res < sum ? sum : res; 
		return;
	}
	if (c%2==1){
		for (int i=0; i<6; i++){
			int nR = r + dirR_le[i];
			int nC = c + dirC_le[i];
			if (checkInBoard(nR, nC) && visited[nR][nC]==0){
				visited[nR][nC] = 1;
				Try(r, c, cnt+1, sum + board[nR][nC]);
				Try(nR, nC, cnt+1, sum + board[nR][nC]);
				visited[nR][nC] = 0;
			}

		}
	}
	else {
		for (int i=0; i<6; i++){
			int nR = r + dirR_chan[i];
			int nC = c + dirC_chan[i];
			if (checkInBoard(nR, nC) && visited[nR][nC]==0){
				visited[nR][nC] = 1;
				Try(r, c, cnt+1, sum + board[nR][nC]);
				Try(nR, nC, cnt+1, sum + board[nR][nC]);
				visited[nR][nC] = 0;
			}

		}
	}
}

void solve() {
	resetData();
	input();
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			visited[i][j] = 1;
			Try (i, j, 1, board[i][j]);		
			visited[i][j] = 0;
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	int test;
	cin >> test;
	for (int i=1; i<=test; i++) {
		solve();
		cout << "Case #" << i << endl << res * res << endl;
	}
	return 0;
}
Leave a Comment