ongnausol
quoc14
c_cpp
22 days ago
2.1 kB
0
Indexable
Never
caidat
#include <iostream> using namespace std; int n,m; int dx[2][6]; int dy[2][6]; int dxc[6] = {-1, 0, 1 , 1, 1, 0}; int dyc[6] = {0, -1, -1, 0, 1, 1}; int dxl[6] = {-1, -1, 0, 1, 0, -1}; int dyl[6] = {0, -1, -1, 0, 1, 1}; int map[100][100]; int kt[100][100]; long long maxans = 0; int inside(int uu, int vv) { if (uu <=0 || uu >= n+1) return 0; if (vv <=0 || vv >= m+1) return 0; return 1; } long long calc(int i, int j) { //vong tron xung quanh 2 truong hop int mod = j%2; long long sum1 = map[i][j]; long long sum2 = map[i][j]; for (int k = 0; k<=4; k+=2) { int uu = i + dx[mod][k]; int vv = j + dy[mod][k]; if (inside(uu,vv)) { sum1 += map[uu][vv]; } uu = i + dx[mod][k+1]; vv = j + dy[mod][k+1]; if (inside(uu,vv)) { sum2 += map[uu][vv]; } } sum1 *= sum1; sum2 *= sum2; return sum1 > sum2 ? sum1 : sum2; } void DFS(int index, int i, int j, int cost) { int mod = (j % 2); for (int k = 0; k <6; k++) { int uu = i + dx[mod][k]; int vv = j + dy[mod][k]; if (inside(uu,vv) && kt[uu][vv]==0) { kt[uu][vv] = 1; long long tmpcost = cost + map[uu][vv]; if (index == 3) { tmpcost*=tmpcost; if (tmpcost > maxans) maxans = tmpcost; } else if (index < 3) { DFS(index + 1, uu, vv, tmpcost); } kt[uu][vv] = 0; } } } void init() { for (int i = 0; i < 6; i++) { dx[0][i] = dxc[i]; dx[1][i] = dxl[i]; dy[0][i] = dyc[i]; dy[1][i] = dyl[i]; } } int main() { init(); //freopen("input.txt","r",stdin); int ntc; cin >> ntc; for (int tc=1; tc<=ntc; tc++) { cin >> m >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> map[i][j]; maxans = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <=m; j++) { long long tmp = calc(i,j); if (tmp > maxans) maxans = tmp; kt[i][j] = 1; DFS(1,i,j,map[i][j]); kt[i][j] = 0; } cout <<"Case #"<<tc<< endl << maxans << endl; } return 0; }
Leave a Comment