Untitled

#include<iostream>
using namespace std;


int T, M, N;
int arr[20][20], visited[20][20];
int Answer;
// -1 0, 0 1, 1 1, 1 0, 1 -1, 0 -1
// -1 0, -1 1, 0 1, 1 0, 0 -1, -1 -1;
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};

bool isValid(int x, int y){
	return x >= 1 && x <= N && y > 0 && y <= M;
}

void bt(int x, int y, int sum, int count){
	if(count == 4){
		if(Answer < sum){
			Answer = sum;
		}
		return;
	}
	for(int i = 0; i < 6; i++){
		if(y % 2 == 0){
			int nx = x + dxc[i];
			int ny = y + dyc[i];
			if(isValid(nx, ny) && visited[nx][ny] == 0 ){
				visited[nx][ny] = 1;
				
				bt(nx, ny, sum+ arr[nx][ny], count+1);
				bt(x,y,sum+arr[nx][ny],count+1);
				visited[nx][ny] = 0;
			}
			
		}
		else{
			int nx = x + dxl[i];
			int ny = y + dyl[i];
			if(isValid(nx, ny) && visited[nx][ny] == 0){
				visited[nx][ny] = 1;
				
				bt(nx, ny, sum+ arr[nx][ny], count+1);
				bt(x,y,sum+arr[nx][ny],count+1);
				visited[nx][ny] = 0;
			}
		}
	}
}

void reset(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			visited[i][j] = 0;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		Answer = 0;
		cin >> M >> N;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				cin >> arr[i][j];
			}
		}
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				visited[i][j] = 1;
				int sum = arr[i][j];
				bt(i, j, sum, 1);
				reset();
			}
		}
		cout << "Case #" <<tc << endl;
		cout <<  long( Answer * Answer) << endl;

	}
	return 0;
}

//
5

5 3

300 410 150 55 370

120 185 440 190 450

165 70 95 420 50

5 5

356 55 41 453 12

401 506 274 506 379

360 281 421 311 489

425 74 276 371 164

138 528 461 477 470

Case #1

2250000

Case #2

3748096
========================================
#include <iostream>
using namespace std;

int n,m,k;
int marketPrice[25];
int sales[35][25];
int need[25];
int have[25];
int res;

bool check(int idx, int item) {
 for (int i = 0; i < sales[idx][1]; i++) {
  if (sales[idx][i+2] == item) return true;
 }
 return false;
}

void solve(int idx, int cost) {
 if (idx == k) {
  res = cost < res ? cost : res;
  return;
 }
 if (cost >= res) return;
 if (have[need[idx]] >= 1) solve(idx+1,cost);
 have[need[idx]]++;
 solve(idx+1,cost+marketPrice[need[idx]]);
 have[need[idx]]--;
 for (int i = 0; i < m; i++) {
  if (check(i,need[idx])) {
   for (int j = 0; j < sales[i][1]; j++) {
    have[sales[i][j+2]]++;
   }
   solve(idx+1,cost+sales[i][0]);
   for (int j = 0; j < sales[i][1]; j++) {
    have[sales[i][j+2]]--;
   }
  }
 }
}

int main() {
 //freopen("input.txt","r",stdin);
 int T;
 cin >> T;
 for (int tc = 1; tc <= T; tc++) {
  cin >> n;
  for (int i = 1; i <= n; i++) {
   cin >> marketPrice[i];
   have[i] = 0;
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
   cin >> sales[i][0] >> sales[i][1];
   for (int j = 0; j < sales[i][1]; j++) {
    cin >> sales[i][j+2];
   }
  }
  cin >> k;
  for (int i = 0; i < k; i++) {
   cin >> need[i];
  }
  res = 999999;
  solve(0,0);
  cout << "#" << tc << " " << res << endl;
 }
 return 0;
}

Input

1          <-- T = 1,

5          <-- Số linh kiện chính của máy tính

20 15 17 18 25            <-- giá chợ Trời của 5 thiết bị từ 1 đến 5 tương ứng

4          <-- 4 gói ưu đãi trên mạng

30 3 1 2 5        <-- gói thứ nhất có giá 30, gồm 3 linh kiện 1, 2, 5

25 2 2 3           <-- gói thứ 2 có giá 25, gồm 2 linh kiện 2, 3

35 3 1 3 5        <-- gói thứ 3 có giá 35, gồm 3 linh kiện 1, 3, 5

20 2 3 4           <-- gói thứ 4 có giá 20, gồm 2 linh kiện 3, 4

3 2 4 5             <-- Số lượng anh Kim cần là 3, lần lượt là 2, 4, 5

Output

#1  48