# HoangLong

user_9175993
plain_text
a month ago
26 kB
13
Indexable
Never
```//HoangLong
//Ban Bong Bay
import java.util.Scanner;

public class Solution {
static int[] map = new int[501];
static int N, score, maxScore;

public static void main(String[] args) throws Exception {
//System.setIn(new FileInputStream("w2_thus/banbongbay/input.txt"));
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();

for (int i = 0; i < N; i++) {
map[i] = sc.nextInt();
}

score = 0;
maxScore = 0;
backtrack(N, 0);

System.out.println("Case #" + tc);
System.out.println(maxScore);
}
sc.close();

}

private static void backtrack(int N, int score) {
int max = -1, curI = 0;
// dkkt
if (N == 0) {
maxScore = maxScore > score ? maxScore : score;
return;
}

if (N == 2) {
int temp = map[0];
if (map[0] < map[1]) {
temp = map[1];
}
backtrack(N - 2, score + 2 * temp);
}

if (N == 3) {
int temp = map[0] * map[2];
if (temp < map[1]) {
backtrack(N - 3, score + 3 * map[1]);
}
}

for (int i = 1; i < N - 1; i++) {
int temp = map[i - 1] * map[i + 1];
int save = map[i];

for (int j = i; j < N - 1; j++) {
map[j] = map[j + 1];
}

backtrack(N - 1, score + temp);

for (int j = N - 2; j > i; j--) {
map[j] = map[j - 1];
}
map[i] = save;
}
}
}
//Ho den
public class Test_1 {
static int T, numberWhole;
static int pointX[], pointY[], value[][], min;
static boolean visited[][];

public static int calculatePoint(int x1, int x2, int y1, int y2){
return ( Math.abs(x2-x1) + Math.abs(y2-y1) );
}

public static void backTrack(int r, int c, int sumTime){
if(sumTime > min) return;

if(min > sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1])){
min = sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1]);
return;
}

for(int i = 1; i <= numberWhole; i++){
visited[value[i][0]][value[i][1]] = true;
visited[value[i][2]][value[i][3]] = true;

if(!visited[value[i][0]][value[i][1]]){
backTrack(value[i][2], value[i][3],
sumTime + value[i][4] + calculatePoint(r, value[i][0], c, value[i][1]));
}

if(!visited[value[i][2]][value[i][3]]){
backTrack(value[i][0], value[i][1],
sumTime + value[i][4] + calculatePoint(r, value[i][2], c, value[i][3]));
}

visited[value[i][0]][value[i][1]] = false;
visited[value[i][2]][value[i][3]] = false;

}
}

public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Test_1"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
numberWhole = scanner.nextInt();
pointX = new int[numberWhole+2];
pointY = new int[numberWhole+2];
pointX[0] = scanner.nextInt();
pointY[0] = scanner.nextInt();
pointX[numberWhole+1] = scanner.nextInt();
pointY[numberWhole+1] = scanner.nextInt();

value = new int[numberWhole+1][5];

for(int i = 1; i <= numberWhole; i++){
value[i][0] = scanner.nextInt();
value[i][1] = scanner.nextInt();
value[i][2] = scanner.nextInt();
value[i][3] = scanner.nextInt();
value[i][4] = scanner.nextInt();
}

visited = new boolean[1001][1001];
min = calculatePoint(pointX[0], pointX[numberWhole+1],
pointY[0], pointY[numberWhole+1]);

visited[pointX[0]][pointY[0]] = true;
backTrack( pointX[0], pointY[0], 0);
System.out.println("#" + tc + " " + min);

}
}

}
//Hugo ve nha
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoVeNha {
static int N;
static int gate[][];
static int res;
static int armyAtGate[], expAtGate[];

static void BT(int k, int cost){
if(k == N){
res = res < cost ? res : cost;
return;
}
if(cost > res)
return;

//Pass
BT(k+1, cost + gate[k][1]);

//Hire
armyAtGate[k] += gate[k][0];
BT(k+1, cost + gate[k][1]*2);
armyAtGate[k] -= gate[k][0];

//Combat
int total = 0;
int tmp_army[] = new int[21];
int tmp_exp[] = new int[21];
for(int i = 0; i < k; i++){
tmp_army[i] = armyAtGate[i];
tmp_exp[i] = expAtGate[i];

if(armyAtGate[i] > 0 && expAtGate[i] < 3){
total += armyAtGate[i];
}
}

int enermy = gate[k][0];
if(total < enermy)
return;

for(int i = 0; i < k; i++){
if(armyAtGate[i] <= 0 || expAtGate[i] >= 3)
continue;
int tmp_enermy = enermy;
enermy -= armyAtGate[i];
armyAtGate[i] -= tmp_enermy;
if(enermy <= 0)
break;
}

for(int i = 0; i < k; i++){
if(armyAtGate[i] > 0 || expAtGate[i] < 3)
expAtGate[i] += 1;
}

BT(k+1, cost);

for(int i = 0; i < k; i++){
armyAtGate[i] = tmp_army[i];
expAtGate[i] = tmp_exp[i];
}
}

public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input_HugoVeNha.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();
for(int t = 1; t <= T; t++){
N = sc.nextInt();
gate = new int[21][2];
for(int i = 0; i < N; i++){
gate[i][0] = sc.nextInt();
gate[i][1] = sc.nextInt();
}

//Solve
res = 999999;
armyAtGate = new int[21];
expAtGate = new int[21];
BT(0, 0);

System.out.println("#" + t + " " + res);
}
}
}
//Hugo thi chay
public class Solution {
static int m, d;
static int []gio, phut, nangLuong, time;
static int timeMin;

public static void backtrack(int k, int energy, int tg, int km){
if(tg > timeMin){
return;
}
if(energy <= 0){
return;
}
if(k >= 5){
return;
}
if(km <= 0){
if(tg < timeMin){
timeMin = tg;
}
return;
}

for(int j=0; j<2; j++){
if(j == 1){
backtrack(k+1, energy-nangLuong[k], tg + time[k], km-1);
backtrack(k, energy-nangLuong[k], tg + time[k], km-1);
}
else{
backtrack(k+1, energy, tg, km);
}
}
}

public static void main(String[] args) {
try {
System.setIn(new FileInputStream("src/hugo_thi_chay/input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner scanner = new Scanner(System.in);
int TC = scanner.nextInt();
for(int t=0; t<TC; t++){
m = scanner.nextInt();
d = scanner.nextInt();
gio = new int[5];
phut = new int[5];
nangLuong = new int[5];
time = new int[5];
for(int i=0; i<5; i++){
gio[i] = scanner.nextInt();
phut[i] = scanner.nextInt();
nangLuong[i] = scanner.nextInt();
}
for(int i=0; i<5; i++){
time[i] = gio[i] * 60 + phut[i];
}

timeMin = Integer.MAX_VALUE;
backtrack(0, m, 0, d);
System.out.println("Case #" + (t+1));
if(timeMin == Integer.MAX_VALUE){
System.out.println(-1);
}
else{
int resGio = timeMin / 60;
int resPhut = timeMin % 60;
System.out.println(resGio + " " + resPhut);
}

}
}
}
//Hugo giao hang
public class hugo_giao_hang {
static int hx, hy, sx, sy, n, Ans;
static int [][] arr, map;
static int [] visit;

static int distance(int i, int j) {
int a = arr[i][0] - arr[j][0];
int b = arr[i][1] - arr[j][1];
if (a < 0) a = 0 - a;
if (b < 0) b = 0 - b;
return a+b;
}

static void createMatrix() {
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
int x = distance(i, j);
map[i][j] = x;
}
}
}

static void Try(int x, int sum_distance, int count) {
if (count == n) {
sum_distance += map[x][n+1];
if (sum_distance < Ans) Ans = sum_distance;
return;
}
if (Ans < sum_distance) return;
for (int i = 1; i <= n; i++) {
if (visit[i] == 0) {
visit[i] = 1;
Try(i, sum_distance + map[x][i], count+1);
visit[i] = 0;
}
}
}

public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("D://Trainee//SRV_training//src//Hugo_Giao_Hang//giao_hang.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
sx = sc.nextInt();
sy = sc.nextInt();
hx = sc.nextInt();
hy = sc.nextInt();
n = sc.nextInt();
arr = new int [n+2][2];
for(int i = 1; i < n+1; i++) {
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
arr[0][0] = sx;
arr[0][1] = sy;
arr[n+1][0] = hx;
arr[n+1][1] = hy;
map = new int [n+2][n+2];
createMatrix();
Ans = 1000000000;
visit = new int [n+2];
visit[0] = 1;
Try(0, 0, 0);

System.out.println("Case #" + test_case + " " + Ans);
}
}
}
//hugo xep lich
public class xep_quang_cao {
static int N, res, start, end;
static int[][] guestTime;
static int[][] score = new int[3][55];
static int[] L = new int[3];
static int[] P = new int[3];

public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("w4_fri/xep_quang_cao/input.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
for (int i = 0; i < 3; i++) {
L[i] = sc.nextInt();
}
for (int i = 0; i < 3; i++) {
P[i] = sc.nextInt();
}
guestTime = new int[N][2];

for (int i = 0; i < N; i++) {
guestTime[i][0] = sc.nextInt();
guestTime[i][1] = sc.nextInt() + guestTime[i][0];
}
start = guestTime[0][0];
end = guestTime[0][1];
for (int i = 1; i < N; i++) {
if (start > guestTime[i][0]) {
start = guestTime[i][0];
}
if (end < guestTime[i][1]) {
end = guestTime[i][1];
}
}
res = -1;

backtrack(0);

System.out.println("Case #" + tc);
System.out.println(res);
}
}

private static boolean checkVisit(int start, int end) {
for (int i = start; i < end; i++) {
return false;
}
return true;
}

private static void visit(int start, int end, int visit) {
for (int i = start; i < end; i++) {
}
}

private static void backtrack(int k) {
if (k == 3) {
int count = sum();
res = count > res ? count : res;
return;
}
for (int i = 1; i <= 50; i++) {
if (checkVisit(i, i + L[k])) {
visit(i, i + L[k], 1);

// Neu ads nam trong thoi gian cua guest thi tinh diem
for (int j = 0; j < N; j++) {
if (i >= guestTime[j][0] && i + L[k] <= guestTime[j][1])
score[k][j] = P[k];
}

backtrack(k + 1);

visit(i, i + L[k], 0);

for (int j = 0; j < N; j++) {
if (i >= guestTime[j][0] && i + L[k] <= guestTime[j][1])
score[k][j] = 0;
}
}

}
}

private static int sum() {
int count = 0;
for (int i = 0; i < N; i++) {
int max = score[0][i];
for (int j = 1; j < 3; j++)
if (max < score[j][i])
max = score[j][i];
count += max;
}
return count;
}
}
//Hugo ban dau
#include<iostream>
using namespace std;
int N, M;
int P; // giới hạn bơm
// mảng 8 loại đường ống
int DuongOng[8][4]={
0,0,0,0,
1,1,1,1,
1,0,1,0,
0,1,0,1,
1,1,0,0,
0,1,1,0,
0,0,1,1,
1,0,0,1 };

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int visit[51][51]; // mảng thăm
int cntN[51][51]; // mảng lan truyền
int map[51][51]; // mang đường ống
int Qx[10000];
int Qy[10000];
int rear, front;
int cnt; //đếm số đường ống

bool check(int x, int y){
if(x >= 0 && x < N && y >= 0 && y < M)return true;
return false;
}
void BFS(int x_mb, int y_mb){
front = rear = 0;
Qx[rear] = x_mb;
Qy[rear++] = y_mb;
visit[x_mb][y_mb] = 1;
cntN[x_mb][y_mb] = 1;
while (front < rear){
int x = Qx[front];
int y = Qy[front++];
for (int i = 0; i < 4; i++){
int nx = x + dx[i]; // vị trí sắp đi đến
int ny = y + dy[i];
if(check(nx, ny)) // check vị trí sắp đi đến
{
if(map[nx][ny] != 0 && visit[nx][ny] == 0 && DuongOng[map[x][y]][i] == 1 && DuongOng[map[nx][ny]][(i+2)%4] == 1)
{ // nếu vị trí sắp tới khác 0, chưa thăm, đầu của 2 loại ống phù hợp nhau
cntN[nx][ny] = cntN[x][y] + 1; // lan truyền giới hạn bơm
if(cntN[nx][ny] > P)return;
cnt++;
Qx[rear] = nx;
Qy[rear++] = ny;
visit[nx][ny] = 1;
}
}
}
}
}
void reset(){
for (int i = 0; i <= N; i++){
for (int j = 0; j <= M; j++){
visit[i][j] = 0;
cntN[i][j] = 0;
}
}
}

int main(){
int T;
int x_mb,y_mb;
freopen("input.txt", "r", stdin);
cin>>T;
for (int tc = 1; tc <= T; tc++)
{
cnt = 1;
cin>>N>>M>>x_mb>>y_mb>>P;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin>>map[i][j];
}
}
reset();
BFS(x_mb,y_mb);
cout<<"Case #"<<tc<<endl;
cout<<cnt<<endl;
}
return 0;
}
//HUgo quan ly tau
#include <iostream>

using namespace std;

int N; // Số lượng người trong dãy
int people[1001], door[4], kc[4][1001], check[5], visit[1001]; // Mảng lưu thông tin về người, cửa, khoảng cách, kiểm tra và viếng thăm
int Max; // Biến lưu trữ kết quả tối ưu

// Hàm in mảng khoảng cách
void print(int kc[]) {
for (int i = 1; i <= N; i++) {
cout << kc[i] << " ";
}
cout << endl;
}

int abs(int x){
return x > 0 ? x : -x;
}

// Hàm backtrack để thực hiện quay lui
void backtrack(int indext, int sum) {
// Nếu đã duyệt hết 4 cửa
if (indext == 4) {
// Lưu kết quả tối ưu
Max = min(Max, sum);
return;
}
// Duyệt qua từng cửa
for (int s = 1; s <= 3; s++) {
// Nếu chưa kiểm tra cửa này
if (check[s] == 0) {
// Duyệt qua 2 trường hợp: mở cửa hoặc không mở
for (int k = 0; k < 2; k++) {
int dor = door[s]; // Cửa hiện tại
int guse = people[dor]; // Số người ở cửa đó
int cout = 0; // Biến đếm số lần di chuyển
int value = 0; // Biến lưu tổng khoảng cách
// Trường hợp mở cửa
if (k == 0) {
check[s] = 1;
while (guse > 0) {
int l = dor - cout; // Cửa bên trái
int r = dor + cout; // Cửa bên phải
// Nếu cửa bên trái hợp lệ và chưa được viếng thăm
if (l >= 1 && visit[l] == 0) {
visit[l] = dor;
value = value + cout + 1; // Cập nhật tổng khoảng cách
guse--; // Giảm số người cần di chuyển
}
// Nếu cửa bên phải hợp lệ và chưa được viếng thăm
else if (r <= N && visit[r] == 0) {
visit[r] = dor;
value = value + cout + 1; // Cập nhật tổng khoảng cách
guse--; // Giảm số người cần di chuyển
}
// Nếu cửa đã được viếng thăm hoặc vượt quá phạm vi
else if ((r <= N && visit[r] != 0) || (l >= 1 && visit[l] != 0)) {
cout++; // Tăng biến đếm
}
}
// Gọi đệ quy cho cửa tiếp theo
backtrack(indext + 1, sum + value);
check[s] = 0; // Đánh dấu cửa đã được kiểm tra
// Đặt lại các cửa đã được viếng thăm
for (int i = 1; i <= N; i++) {
if (visit[i] == dor)
visit[i] = 0;
}
}
// Trường hợp không mở cửa
else {
check[s] = 1;
while (guse > 0) {
int l = dor - cout; // Cửa bên trái
int r = dor + cout; // Cửa bên phải
if (r <= N && visit[r] == 0) { // Nếu cửa bên phải hợp lệ và chưa được viếng thăm
visit[r] = dor;
value = value + cout + 1;
guse--;
}
else if (l >= 1 && visit[l] == 0) { // Nếu cửa bên trái hợp lệ và chưa được viếng thăm
visit[l] = dor;
value = value + cout + 1;
guse--;
} else {
cout++;
}
}
// Gọi đệ quy cho cửa tiếp theo
backtrack(indext + 1, sum + value);
check[s] = 0; // Đánh dấu cửa đã được kiểm tra
// Đặt lại các cửa đã được viếng thăm
for (int i = 1; i <= N; i++) {
if (visit[i] == dor)
visit[i] = 0;
}
}
}
}
}
}

int main() {
//freopen("HugoQuanLy.txt", "r", stdin);
int T;
cin >> T; // Nhập số lượng bộ test
for (int t = 1; t <= T; t++) {
cin >> N; // Nhập số lượng người trong dãy
// Nhập thông tin về cửa và số người ở mỗi cửa
for (int i = 1; i <= 3; i++) {
int x;
cin >> x;
door[i] = x;
cin >> people[x];
}
// Tính toán khoảng cách từ mỗi cửa đến từng người
for (int i = 1; i <= 3; i++) {
int k = door[i];
for (int j = 1; j <= N; j++) {
kc[i][j] = abs(k - j) + 1;
}
}
Max = 10000; // Khởi tạo kết quả tối ưu
backtrack(1, 0); // Gọi hàm backtrack để tìm kết quả tối ưu
// In kết quả
cout << "Case #" << t << endl;
cout << Max << endl;
}

return 0;
}
//Thong tri khu vuc
#include<iostream>
using namespace std;
// code 100/100
int map[105][105];
int mapCopy[105][105];
int visit[105][105];
int Que[10000][2];
int n, ans, T;
int TS[6]; // mảng lưu tần số xuất hiện của các số
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1,0, 1,0 };
void reset() {
for (int i = 0; i < 6; i++)  TS[i] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) visit[i][j] = 0;
}
}
void dfs(int x, int y, int oVal, int nVal) {           // Tô màu cho cửa hàng
for (int h = 0; h < 4; h++) {
int nx = x + dx[h];
int ny = y + dy[h];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (!visit[nx][ny] && mapCopy[nx][ny] == oVal) {
visit[nx][ny] = 1;
mapCopy[nx][ny] = nVal;
dfs(nx, ny, oVal, nVal);
}
}
}
void bfs(int x, int y) {
reset();
visit[x][y] = 1;
int front = 0, rear = 0;
Que[rear][0] = x; // push vị trí đầu vào Queue
Que[rear++][1] = y;
while (front < rear) {
int r = Que[front][0]; // vị trí đang đứng
int c = Que[front++][1];
for (int h = 0; h < 4; h++) {
int nx = r + dx[h]; // vị trí sắp đến
int ny = c + dy[h];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // check vị trí sắp đến
if (!visit[nx][ny]) { // nếu vị trí sắp tới chưa được thăm
if ((map[r][c] == 0) || (map[nx][ny] == map[r][c])) {
TS[map[nx][ny]] ++;                    // Tăng tần số xuất hiện cho số đó
visit[nx][ny] = 1; // đánh dấu
Que[rear][0] = nx; // push số đó vào Queue
Que[rear++][1] = ny;
}
}
}
}
int maxTS = TS[1], color = 1;
for (int i = 2; i <= 5; i++)
if (TS[i] >= maxTS) {              // Chọn ra số có tần số xuất hiện nhiều nhât
color = i;
maxTS = TS[i];
}
mapCopy[x][y] = color;
dfs(x, y, 0, color);
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mapCopy[i][j] == 0) {
bfs(i, j);
}
}
}
reset();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visit[i][j]) {                      // Tìm số vùng
ans++;
visit[i][j] = 1;
dfs(i, j, mapCopy[i][j], mapCopy[i][j]);
}
}
}
}
int main() {
freopen("input.txt", "r", stdin);
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
mapCopy[i][j] = map[i][j];
}
}
ans = 0; solve();
cout << "Case #" << tc << endl << ans << endl;
}
return 0;
}
//Cleaning robot
#include<iostream>

using namespace std;

int M[101][101];
int visited[101][101];
int A[2][100];
int idx;
int ke[101][101];
int S[2][1000000];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
int top;
int bot;
int luu[11];
int used[11];
int minn,kq;

bool checkused()
{
for(int i=0;i<idx;i++)
{
if(used[i]==0) return true;
}
return false;
}

void tinhtoan(int x)
{
if(kq>minn) return;
if(!checkused())
{
if(kq<minn) minn=kq;
return;
}
for(int i=0;i<idx;i++)
{
if(used[i]==0)
{
kq+=ke[x][i];
used[i]=1;
tinhtoan(i);
used[i]=0;
kq-=ke[x][i];
}
}
}

int main()
{
//freopen("input.txt","r",stdin);
int t;cin>>t;

for(int tc=1;tc<=t;tc++)
{
idx=1;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>M[i][j];
if(M[i][j]==3)
{
A[0][0]=i;
A[1][0]=j;
}
else if(M[i][j]==1)
{
A[0][idx]=i;
A[1][idx]=j;
idx++;
}
}
}
// xu ly
for(int i=0;i<101;i++)
for(int j=0;j<101;j++) ke[i][j]=0;
//
int dem=0;
bool firstcheck=true;
for(int i=0;i<idx;i++)
{
for(int a=0;a<101;a++)
for(int b=0;b<101;b++) visited[a][b]=0;
//khai bao queue
top=-1,bot=-1;
//
top++;
S[0][top]=A[0][i];
S[1][top]=A[1][i];
visited[A[0][i]][A[1][i]]=1;
//
while(top!=bot)
{
bot++;
int x=S[0][bot];
int y=S[1][bot];
//
for(int k=0;k<4;k++)
{
int xnew=x+dx[k];
int ynew=y+dy[k];
if(xnew >=0 && xnew <n && ynew >= 0 && ynew<m)
{
if(visited[xnew][ynew]==0 && M[xnew][ynew]!=2)
{
top++;
S[0][top]=xnew;
S[1][top]=ynew;
visited[xnew][ynew]=visited[x][y]+1;
}
}
}
}
//dua vao ma tran ke
for(int a=0;a<idx;a++)
{
ke[i][a]=visited[A[0][a]][A[1][a]]-1;
if(ke[i][a]==-1) firstcheck=false;
}
if(firstcheck) dem++;
}
if(dem<idx)
{
cout<<"Case #"<<tc<<endl<<-1<<endl;
continue;
}
minn=9999;kq=0;
for(int k=0;k<11;k++) used[k]=0;
//
tinhtoan(0);
//
cout<<"Case #"<<tc<<endl;
cout<<minn<<endl;
}
return 0;
}
//Ho den
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Test_1 {
static int T, numberWhole;
static int pointX[], pointY[], value[][], min;
static boolean visited[][];

public static int calculatePoint(int x1, int x2, int y1, int y2){
return ( Math.abs(x2-x1) + Math.abs(y2-y1) );
}

public static void backTrack(int r, int c, int sumTime){
if(sumTime > min) return;

if(min > sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1])){
min = sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1]);
return;
}

for(int i = 1; i <= numberWhole; i++){
visited[value[i][0]][value[i][1]] = true;
visited[value[i][2]][value[i][3]] = true;

if(!visited[value[i][0]][value[i][1]]){
backTrack(value[i][2], value[i][3],
sumTime + value[i][4] + calculatePoint(r, value[i][0], c, value[i][1]));
}

if(!visited[value[i][2]][value[i][3]]){
backTrack(value[i][0], value[i][1],
sumTime + value[i][4] + calculatePoint(r, value[i][2], c, value[i][3]));
}

visited[value[i][0]][value[i][1]] = false;
visited[value[i][2]][value[i][3]] = false;

}
}

public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Test_1"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
numberWhole = scanner.nextInt();
pointX = new int[numberWhole+2];
pointY = new int[numberWhole+2];
pointX[0] = scanner.nextInt();
pointY[0] = scanner.nextInt();
pointX[numberWhole+1] = scanner.nextInt();
pointY[numberWhole+1] = scanner.nextInt();

value = new int[numberWhole+1][5];

for(int i = 1; i <= numberWhole; i++){
value[i][0] = scanner.nextInt();
value[i][1] = scanner.nextInt();
value[i][2] = scanner.nextInt();
value[i][3] = scanner.nextInt();
value[i][4] = scanner.nextInt();
}

visited = new boolean[1001][1001];
min = calculatePoint(pointX[0], pointX[numberWhole+1],
pointY[0], pointY[numberWhole+1]);

visited[pointX[0]][pointY[0]] = true;
backTrack( pointX[0], pointY[0], 0);
System.out.println("#" + tc + " " + min);

}
}

}

```