input.txt

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class AdvertisementSchedule {
	static int n, lastTime, Answer;
	static int[] lenAd = new int[3], pointAd = new int[3], choose = new int[3], start = new int[3];
	static int[][] visitor = new int[50][2];
	static int[] point = new int[50];

	// k là số thứ tự quảng cáo đã được đặt
	public static void advertise(int k, int startTime) {
		if (k == 3) {
			// reset diem cua N nguoi
			for (int i = 0; i < n; i++) {
				point[i] = 0;
			}
			// duyet 3 quang cao, tinh diem cho n nguoi voi moi quang cao
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < n; j++) {
					if (visitor[j][0] <= start[i] && visitor[j][1] >= (start[i] + lenAd[choose[i]])) {
						point[j] = Math.max(point[j], pointAd[choose[i]]);
					}
				}
			}
			int sumPoint = 0;
			for (int i = 0; i < n; i++) {
				sumPoint += point[i];
			}
			Answer = Math.max(Answer, sumPoint);
			return;
		}
		// sinh tổ hơp từ startTime
		for (int i = startTime; i <= lastTime; i++) {
			start[k] = i; // thoi gian bat dau quang cao thu k
			advertise(k + 1, i + lenAd[choose[k]]);
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\Ads_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; ++tc) {
			// lastTime la thoi gian nguoi cuoi cung roi di
			Answer = lastTime = 0;
			n = sc.nextInt();
			lenAd[0] = sc.nextInt();
			lenAd[1] = sc.nextInt();
			lenAd[2] = sc.nextInt();
			pointAd[0] = sc.nextInt();
			pointAd[1] = sc.nextInt();
			pointAd[2] = sc.nextInt();
			for (int i = 0; i < n; i++) {
				visitor[i][0] = sc.nextInt(); // thoi gian den
				visitor[i][1] = sc.nextInt(); // thoi gian o lai
				visitor[i][1] += visitor[i][0]; // thoi gian roi di
				if (visitor[i][1] > lastTime) {
					lastTime = visitor[i][1];
				}
			}
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					for (int k = 0; k < 3; k++) {
						if (i != j && j != k && k != i) {
							// các hoán vị đặt quảng cáo
							choose[0] = i;
							choose[1] = j;
							choose[2] = k;
							advertise(0, 0);
						}
					}
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(Answer);
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class ArrayGame {
	static int N, point;
	static int[] arr;
	static long sum, Answer;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\ArrayGame_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			arr = new int[N];
			sum = 0;
			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
				sum += arr[i];
			}
			point = 0;
			Answer = 0;

			if (sum == 0) {
				System.out.println(N - 1);
				continue;
			}
			backtrack(0, N - 1, sum, 0);
			System.out.println(Answer);

		} // for tc
	}

	public static void backtrack(int start, int end, long sum, int point) {
		if (sum % 2 == 1) {
			return;
		}
		// cong don cho den khi nao khong vuot qua sum/2
		long tempSum = 0;
		for (int i = start; i < end; i++) { // chia lam hai phan nen khong duoc
											// <= end
			tempSum += arr[i];
			if (tempSum > sum / 2) {
				return;
			} else if (tempSum == sum / 2) {
				point++;
				Answer = Math.max(point, Answer);
				backtrack(start, i, sum / 2, point);
				backtrack(i + 1, end, sum / 2, point);
				// point--;
				break;
// da tim duoc diem chia doi thi break vi khong can duyet nua
// neu khong kep point vao ham thi phai de point--
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BanBong {
	static int N;
	static int[] arr;
	static boolean[] shot;
	static long Answer, Sum;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\BanBong_input.txt"));
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		for (int i = 1; i <= tc; i++) {
			N = sc.nextInt();
			arr = new int[N];
			for (int j = 0; j < N; j++) {
				arr[j] = sc.nextInt();
			}
			Answer = 0;
			Sum = 0;
			shot = new boolean[N];
			balloon(1);
			System.out.println("#" + i + " " + Answer);
		}
	}

	// k = ballon index
	public static void balloon(int k) {
		if (k == N - 1) { // chưa chọn quả bóng thứ N-1, N
			long temp = Sum;
			int a = -1, b = -1;
			for (int i = 0; i < N; i++) {
				if (!shot[i]) {
					if (a == -1)
						a = arr[i];
					else
						b = arr[i];
				}
			}
// quả nào lớn hơn thì chọn bắn quả nhỏ để có số điểm là 2 lần quả lớn hơn
			if (a > b) {
				temp += a * 2;
			} else {
				temp += b * 2;
			}
			Answer = Math.max(Answer, temp);
			return;
		}
		// hàm sinh mọi khả năng bắn quả đầu tiên
		for (int i = 0; i < N; i++) {
			if (!shot[i]) {
				shot[i] = true;
				int a = 1, b = 1; // a = right ballon, b = left ballon
				for (int j = i + 1; j < N; j++) {
					if (!shot[j]) {
						a = arr[j];
						break;
					}
				}
				for (int j = i - 1; j >= 0; j--) {
					if (!shot[j]) {
						b = arr[j];
						break;
					}
				}
				// nếu ở biên thì a hoặc b sẽ vẫn là 1
				Sum += a * b;
				balloon(k + 1); // chọn quả bóng tiếp theo

				// hoàn nguyên
				shot[i] = false;
				Sum -= a * b;

			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BieuThucZero {
	static int N;
	static int[] arr;
	static int result;
	static int[] visited; // xác định dấu ở mỗi step
	// visited[i] là dấu đứng giữa arr[i] và arr[i+1]
	static int count;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\BieuThucZero_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			arr = new int[N];
			count = 0; // dem so cach dat
			visited = new int[N];
			reset();
			Solve(0);
			System.out.println(count);
		}
	}

	public static void reset() {
		for (int i = 0; i < N; i++) {
			arr[i] = i + 1;
		}
	}

// goi step den N-2 thi ben trong moi xac dinh dau cho visited[N-2] roi goi de quy toi
// Solve(N-1) --> luc nay ham Solve(N-1) se goi ham tinh toan va ket thuc
// chu khong xac dinh dau cho visited[N-1]
// dau cuoi cung la step = N-2, duoc dat ngay sau arr[N-2]
	public static void Solve(int step) {
		if (step == N - 1) { // N step tu 0 toi N-1
			int kq = Cal();
			if (kq == 0) {
				count++;
			}
			reset(); // quan trọng
			return;
		}
// với mỗi step, bạn buộc phải có 1 trong 3 lựa chọn nên chẳng có gì phải hoàn nguyên cả
		visited[step] = 0; // khong dau
		Solve(step + 1);

		visited[step] = 1; // dau +
		Solve(step + 1);

		visited[step] = 2; // dau -
		Solve(step + 1);
		// visited[step] = 0;
	}

	public static int Cal() {
		for (int i = 0; i < N - 1; i++) { // < N-1 vi xet arr[i+1]
			if (visited[i] == 0) {
// không được viết arr[i] = arr[i] * 10 + arr[i + 1]; vì có thể còn viết liền tiếp cho i+2 ...
				arr[i + 1] = arr[i] * 10 + arr[i + 1];
				arr[i] = 0;
			}
		}
// ban đầu dấu là '+'
// nếu gặp visited = 0 thì dấu sẽ không đổi --> chỗ không dấu sẽ được đổi thành + hoặc - 
		int sum = 0;
		char dau = '+';
		for (int i = 0; i < N; i++) {
			if (dau == '+') {
				sum += arr[i];
			} else {
				sum -= arr[i];
			}
			if (visited[i] == 1) {
				dau = '+';
			}
			if (visited[i] == 2) {
				dau = '-';
			}
		}
		return sum;
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class CheckingCube_Optimal {
	static int N, Answer, lim;

	// pre la maxLimit, duoc xac dinh boi so truoc no nen goi la pre.
	static void backTrack(int k, int sum, int pre) {
		if (sum > N) {
			return;
		}
		if (k == 5) {
			if (sum == N) {
				Answer++;
			}
			return;
		}
		for (int i = pre; i >= 0; i--) {
			backTrack(k + 1, sum + i * i * i, i);
		}
	}

	public static void main(String[] args) throws FileNotFoundException {

		System.setIn(new FileInputStream("src\\Backtrack\\CheckingCube_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			Answer = 0;
			for (lim = 0; lim * lim * lim <= N; lim++)
				;
			backTrack(0, 0, lim - 1);
			System.out.println("#" + tc + " " + Answer);
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class ChessRook_Optimal {
	static int N;
	static int[][] board;
	static int maxRook, countRook;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\ChessRook_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			board = new int[N][N];
			for (int i = 0; i < N; i++) {
				String line = sc.next();
				for (int j = 0; j < N; j++) {
					if (line.charAt(j) == 'X') {
						board[i][j] = 1; // ô có tường
					}
				}
			}
			maxRook = -1;
			countRook = 0;
			Backtrack(0);
			System.out.println("Case #" + tc);
			System.out.println(maxRook);

		} // for tc
	}

	// k là index mỗi ô của board
	public static void Backtrack(int k) {
		if (k == N * N) {
			maxRook = Math.max(maxRook, countRook);
			return;
		}
		int row = k / N;
		int col = k % N;

		if (canSetRook(row, col)) {
			board[row][col] = 2; // đặt Xe
			countRook += 1;
			Backtrack(k + 1); // đặt ô tiếp

			board[row][col] = 0;
			countRook -= 1;
			Backtrack(k + 1);
		} else {
			Backtrack(k + 1);
		}
	}

	public static boolean canSetRook(int r, int c) {
		if (board[r][c] == 1 || board[r][c] == 2) {
			return false;
		}

		for (int i = c - 1; i >= 0; i--) {
			if (board[r][i] == 2)
				return false;
			else if (board[r][i] == 1)
				break;
		}

		for (int i = r - 1; i >= 0; i--) {
			if (board[i][c] == 2)
				return false;
			else if (board[i][c] == 1)
				break;
		}

		return true;
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class ConnectProcessor {
	static int N, nC; // number of cores
	static int[][] board, visit, Core;
	static int Answer;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream(
				"src\\Backtrack\\ConnectProcessor_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			board = new int[20][20];
			Core = new int[20][2];
			nC = 0;
			visit = new int[20][20];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					board[i][j] = sc.nextInt();
					if (board[i][j] == 1) {
						Core[nC][0] = i;
						Core[nC][1] = j;
						visit[i][j] = 1;
						nC++;
					}
				}
			}
			Answer = 19081998;
			Try(0, 0);
			if (Answer == 19081998) {
				System.out.println("#" + tc + " " + -1);
			} else {
				System.out.println("#" + tc + " " + Answer);
			}
		}
	}

	public static boolean check(int i, int d) {
		int nx = Core[i][0] + dx[d];
		int ny = Core[i][1] + dy[d];
		while (nx >= 0 && nx < N && ny >= 0 && ny < N) {
			if (visit[nx][ny] == 1) {
				return false;
			}
			nx = nx + dx[d];
			ny = ny + dy[d];
		}
		return true;
	}

	// dùng để vừa nối dây và gỡ dây
	public static int setWires(int i, int d) {
		int lenWire = 0;
		int nx = Core[i][0] + dx[d];
		int ny = Core[i][1] + dy[d];
		while (nx >= 0 && nx < N && ny >= 0 && ny < N) {
			visit[nx][ny] = 1 - visit[nx][ny];
			lenWire++;
			nx = nx + dx[d];
			ny = ny + dy[d];
		}
		return lenWire;
	}

	public static void Try(int i, int sumWire) {
		if (i == nC) {
			Answer = Math.min(sumWire, Answer);
			return;
		}
		for (int d = 0; d < 4; d++) {
			if (check(i, d)) {
				sumWire += setWires(i, d);
				Try(i + 1, sumWire);
				sumWire -= setWires(i, d);
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class DiAnCuoi {
	static int n, m;
	static int[][] graph;
	static int[] visited;
	static int minVertex;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\DiAnCuoi_input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t-- > 0) {
			n = sc.nextInt();
			m = sc.nextInt();
			graph = new int[n + 1][n + 1];

			for (int i = 0; i < m; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				graph[u][v] = 1;
			}
			visited = new int[n + 1];
			visited[1] = 1;
			minVertex = Integer.MAX_VALUE;
			dfsLuotDi(1, 1);
			System.out.println(minVertex);
		}
	}

	public static void dfsLuotDi(int u, int count) {
		if (count > minVertex) {
			return;
		}
		if (u == 2) {
			dfsLuotVe(2, count);
			return;
		}

		for (int v = 1; v <= n; v++) {
			if (graph[u][v] == 1) {
				if (visited[v] == 0) {
					visited[v]++;
					dfsLuotDi(v, count + 1);
					visited[v]--;
				}
			}
		}
	}

	public static void dfsLuotVe(int u, int count) {
		if (count > minVertex || (count == minVertex && u != 1)) {
			return;
		}
		if (u == 1) {
			minVertex = Math.min(minVertex, count);
			return;
		}
		for (int v = 1; v <= n; v++) {
			if (graph[u][v] == 1) {
				if (visited[v] <= 1) {
					visited[v]++;
					if (visited[v] == 1) {
						dfsLuotVe(v, count + 1);
					} else {
						dfsLuotVe(v, count);
					}
					visited[v]--;
				}
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class DiChuyenBo {
	static int M, N;
	static int[] Weight;
	static int Answer;
	static int Sum;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\DiChuyenBo_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			M = sc.nextInt();
			N = sc.nextInt();
			Weight = new int[N];
			for (int i = 0; i < N; i++) {
				Weight[i] = sc.nextInt();
			}
			Answer = -1;
			Backtrack(0, 0);
			System.out.println("#" + tc + " " + Answer);
		}
	}

	public static void Backtrack(int k, int sum) {
		if (sum > M) {
			return;
		}
		if (k == N) {
			if (sum > Answer) {
				Answer = sum;
			}
			return;
		}
		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				Backtrack(k + 1, sum);
			} else {
				Backtrack(k + 1, sum + Weight[k]);
			}
		}
	}

}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class EightQueens_Optimal1 {
	static int[][] board = new int[8][8];
	static int[] pos = new int[8]; // mang danh dau
	static int maxScore;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\8QueensMaxScore_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int k = sc.nextInt(); // so ban co trong mot testcase
			System.out.println("Case #" + tc);
			for (int b = 0; b < k; b++) {
				for (int i = 0; i < 8; i++)
					for (int j = 0; j < 8; j++)
						board[i][j] = sc.nextInt();
				maxScore = 0;
				Go(0, 0);
				System.out.println(maxScore);
			}
		}
	}

	// đặt theo từng hàng
	static void Go(int r, int score) {
		if (r == 8) {
			maxScore = Math.max(maxScore, score);
			return;
		}
		for (int c = 0; c < 8; c++) {
			if (check(r, c)) {
				pos[r] = c;
				Go(r + 1, score + board[r][c]); // đặt hàng tiếp
				// pos[r] = 0;
				// không cần hoàn nguyên vì sẽ tự được gán lại, coi như là không đặt
			}
		}
	}

	static boolean check(int r, int c) {
		// cùng cột hàng trên và 2 đường chéo phía trên
		// i, pos[i] là cặp tọa độ của ô có Hậu
		for (int i = 0; i < r; i++) {
			if (pos[i] == c) {
				return false;
			}
			if (r - i == Math.abs(c - pos[i])) {
				return false;
			}
		}
		return true;
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class EightQueens_Optimal2 {
	static int maxSum;
	static int[][] board;
	static boolean[][] visitHau;

	// static int numSolutions;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\8QueensMaxScore_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int k = sc.nextInt();
			System.out.println("Case #" + tc);
			for (int i = 0; i < k; i++) {
				board = new int[8][8];
				for (int j = 0; j < 8; j++) {
					for (int j2 = 0; j2 < 8; j2++) {
						board[j][j2] = sc.nextInt();
					}
				}
				maxSum = 0;
				visitHau = new boolean[8][8];
				// numSolutions = 0;
				BacktrackSolve(0);
				System.out.println(maxSum);
				// System.out.println(numSolutions);

			} // bang
		}
	}

	public static void BacktrackSolve(int row) {
		if (row == 8) { // da dat het hau -> tinh tong
			int sum = 0;
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8; j++) {
					if (visitHau[i][j]) {
						sum += board[i][j];
					}
				}
			}
			maxSum = Math.max(maxSum, sum);
			// numSolutions++;
			return;
		}
		for (int col = 0; col < 8; col++) {
			if (checkSafe(row, col)) {
				visitHau[row][col] = true; // dat hau
				BacktrackSolve(row + 1);
				visitHau[row][col] = false;
			}
		}
	}

	public static boolean isSafe(int row, int col) {
		// cùng cột, hàng trên
		for (int x = 0; x < row; x++) {
			if (visitHau[x][col]) {
				return false;
			}
		}
		for (int x = row - 1, y = col - 1; x >= 0 && y >= 0; x--, y--) {
			if (visitHau[x][y]) {
				return false;
			}
		}

		for (int x = row - 1, y = col + 1; x >= 0 && y < 8; x--, y++) {
			if (visitHau[x][y]) {
				return false;
			}
		}
		return true;
	}

	public static boolean checkSafe(int row, int col) {
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < 8; j++) {
				if (visitHau[i][j]) {
					if (col == j || Math.abs(row - i) == Math.abs(col - j)) {
						return false;
					}
				}
			}
		}
		return true;
	}
}

package Backtrack;

// gần giống y hệt bài cleaning robot
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoGiaoHang {
	static int N;
	static int[] x = new int[12], y = new int[12];
	static int[][] matrix = new int[12][12]; // matrix kề lưu khoảng cách giữa N điểm
	static int[] visit = new int[12];
	static int minWay;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\HugoGiaoHang_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			x[0] = sc.nextInt(); // xSamsung
			y[0] = sc.nextInt();
			x[1] = sc.nextInt(); // xHome
			y[1] = sc.nextInt();
			visit[0] = visit[1] = 1;
			N = sc.nextInt(); // N địa điểm giao hàng
			for (int i = 0; i < N; i++) {
				x[i + 2] = sc.nextInt();
				y[i + 2] = sc.nextInt();
			}
			matrixDistance(); // sinh matrix khoảng cách
			minWay = Integer.MAX_VALUE;
			// Solve(position, step, distance);
			Solve(0, 0, 0);
			System.out.println("Case #" + tc + " " + minWay);
		}
	}

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

	static void matrixDistance() {
		for (int i = 0; i <= N; i++) {
			for (int j = i + 1; j <= N + 1; j++) {
				matrix[i][j] = matrix[j][i] = calDistance(x[i], y[i], x[j], y[j]);
			}
		}
	}

	// distance là kết quả cuối nhánh, tổng khoảng cách
	// step là số địa điểm giao hàng đã hoàn thành - 0
	// position là vị trí được lựa chọn - x[0], y[0] - công ty Samsung - preNode
	static void Solve(int position, int step, int distance) {
		if (distance > minWay) {
			return;
		}
		if (step == N) {
			// khoảng cách từ địa điểm được giao cuối cùng về nhà
			int KQ = distance + matrix[position][1];
			minWay = Math.min(minWay, KQ);
			return;
		}
		for (int i = 2; i <= N + 1; i++) {
			if (visit[i] == 0) {
				visit[i] = 1;
				Solve(i, step + 1, distance + matrix[position][i]);
				visit[i] = 0;
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoOng_DFS {
	static int N, M;
	static int[][] arr = new int[15][15];
	static int[][] visit = new int[15][15];
	static int[] dx = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int[] dy = { -1, 0, 1, 1, 1, 0, -1, -1 };
	static long Answer;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\HugoOng_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; ++tc) {
			Answer = 0;
			M = sc.nextInt();
			N = sc.nextInt();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					arr[i][j] = sc.nextInt(); // luong mat
					visit[i][j] = 0;
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (visit[i][j] == 0) {
						visit[i][j] = 1;
						dfs(i, j, 1, arr[i][j]);
						// visit[i][j] = 0;
					}
				}
			}

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

	public static void dfs(int x, int y, int k, int sum) {
		if (k == 4) {
			Answer = Math.max(Answer, sum);
			return;
		}
		for (int i = 0; i < 8; i++) {
			if (y % 2 == 1 && (i == 0 || i == 2)) {
				continue;
			} else if (y % 2 == 0 && (i == 4 || i == 6)) {
				continue;
			} else {
				int nextX = x + dx[i];
				int nextY = y + dy[i];
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M) {
					if (visit[nextX][nextY] == 0) {
						visit[nextX][nextY] = 1;
						dfs(nextX, nextY, k + 1, sum + arr[nextX][nextY]);
						dfs(x, y, k + 1, sum + arr[nextX][nextY]);
						visit[nextX][nextY] = 0;
					}
				}
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.util.Scanner;

public class HugoQuanLyTau {
	static Scanner sc;
	static int hoanvi[][] = { { 1, 2, 3 }, { 1, 3, 2 }, { 2, 1, 3 }, { 2, 3, 1 }, { 3, 1, 2 }, { 3, 2, 1 } };
	static int gate[][];
	static int cong[][];
	static int visited[];
	static int N, Answer;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src\\Backtrack\\HugoQuanLyTau_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			Answer = Integer.MAX_VALUE;
			gate = new int[4][2];
			for (int i = 1; i <= 3; i++) {
				gate[i][0] = sc.nextInt(); // ví trí
				gate[i][1] = sc.nextInt(); // số lượng khách
			}
			// 6 hoan vi dai dien cho thứ tự mở đóng cổng khác nhau
			for (int i = 0; i < 6; i++) {
				// stt cong mo lan luot la c1, c2, c3
				int c1 = hoanvi[i][0];
				int c2 = hoanvi[i][1];
				int c3 = hoanvi[i][2];
				visited = new int[N + 1];
				cong = new int[4][2];
				cong[1][0] = gate[c1][0];
				cong[1][1] = gate[c1][1];
				cong[2][0] = gate[c2][0];
				cong[2][1] = gate[c2][1];
				cong[3][0] = gate[c3][0];
				cong[3][1] = gate[c3][1];

				// backtrack(idxGate, sumDistance);
				backtrack(1, 0);
			}
			System.out.println("Case #" + tc + "\n" + Answer);
		}
	}

	static void backtrack(int idxGate, int sumDistance) {
		if (idxGate == 4) {
			Answer = Math.min(Answer, sumDistance);
			return;
		}
		int pos = cong[idxGate][0]; // vị trí cổng đang xét
		int numPeople = cong[idxGate][1];
		int distance = 1;
		int left = pos, right = pos;
		// đưa người đầu tiên vào vị trí ngay trước cửa
		if (visited[pos] == 0) {
			visited[pos] = idxGate;
			numPeople--;
			sumDistance = sumDistance + distance;
		}
		// phân bố đều sang 2 bên
		while (numPeople > 0) {
			if (left > 1) {
				left--;
			}
			if (right < N) {
				right++;
			}
			distance++;

			if (numPeople == 1) {
				// trường hợp cả 2 bên đều trống
				if (visited[left] == 0 && visited[right] == 0) {
					visited[left] = idxGate;
					backtrack(idxGate + 1, sumDistance + distance);
					visited[left] = 0;
					// hoàn nguyên các vị trí được dánh dấu bên trong dfs
					for (int i = 1; i <= N; i++) {
						if (visited[i] > idxGate) {
							visited[i] = 0;
						}
					}
					visited[right] = idxGate;
					backtrack(idxGate + 1, sumDistance + distance);
					visited[right] = 0;
					for (int i = 1; i <= N; i++) {
						if (visited[i] > idxGate) {
							visited[i] = 0;
						}
					}
					// Quan trọng: chấm dứt nhánh backtrack này
					return;
				}
			}

			// nếu numPeople >= 2 chạy vào 2 if dưới
			// nếu numPeople = 1, và 1 trong hai phía còn trống, 1 trong 2 if
			// dưới sẽ được chọn
			if (visited[left] == 0) {
				visited[left] = idxGate;
				numPeople--;
				sumDistance = sumDistance + distance;
			}
			if (visited[right] == 0) {
				visited[right] = idxGate;
				numPeople--;
				sumDistance = sumDistance + distance;
			}
		}

		// chọn cổng tiếp
		backtrack(idxGate + 1, sumDistance);
	}

}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoThiChay {
	static int M, distance;
	static int Answer;

	// thay cho mang hai chieu, lưu 5 kiểu chạy
	static class Run {
		int minute, sec, energy;
	}

	static Run[] run;
	static boolean success;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\HugoThiChay_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; ++tc) {
			M = sc.nextInt();
			distance = sc.nextInt();
			run = new Run[5];
			for (int i = 0; i < 5; i++) {
				run[i] = new Run();
				run[i].minute = sc.nextInt();
				run[i].sec = sc.nextInt();
				run[i].energy = sc.nextInt();
				run[i].sec += run[i].minute * 60;
			}
			Answer = Integer.MAX_VALUE;
			success = false;
			// hugo(int start, int k, int sumT, int sumE)
			hugo(0, 0, 0, 0);
			System.out.println("Case #" + tc);
			if (success) {
				int minutes, seconds;
				minutes = Answer / 60;
				seconds = Answer - minutes * 60;
				System.out.println(minutes + " " + seconds);
			} else {
				System.out.println(-1);
			}
		}
	}

	// start là index xuất phát của kiểu chạy được chọn, sử dụng để không sinh
	// tổ hợp lặp
	static void hugo(int start, int kmRun, int sumT, int sumE) {
		// 2 kiểu cắt nhánh
		if (sumE > M) {
			return;
		}
		if (sumT >= Answer) {
			return;
		}
		if (kmRun == distance) {
			success = true;
			Answer = Math.min(Answer, sumT);
			return;
		}
		for (int i = start; i < 5; i++) {
			hugo(i, kmRun + 1, sumT + run[i].sec, sumE + run[i].energy);
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoVeNha {
	static int Answer, N;
	static int[][] gate = new int[20][2];
	static int sum, temp;
	static int[] army = new int[4];

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\HugoVeNha_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; ++tc) {
			Answer = 1000000;
			N = sc.nextInt();
			for (int i = 0; i < N; i++) {
				gate[i][0] = sc.nextInt(); // số lính
				gate[i][1] = sc.nextInt(); // phí cổng
			}
			army[3] = army[2] = army[1] = 0;
			comeHome(0, 0);

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

	public static void comeHome(int k, int cost) {
		if (k == N) {
			Answer = Math.min(Answer, cost);
			return;
		}
		if (cost >= Answer) {
			return;
		}
		// TH1 - pass
		comeHome(k + 1, cost + gate[k][1]);

		// TH2 - hire
		int fresher = army[3];
		int junior = army[2];
		int senior = army[1];
		army[3] += gate[k][0];
		comeHome(k + 1, cost + gate[k][1] * 2);
		army[3] = fresher;

		// TH3 - battle
		sum = army[3] + army[2] + army[1];
		if (sum >= gate[k][0]) {
			temp = gate[k][0];
			for (int i = 1; i <= 3; i++) {
				if (temp > 0) {
					if (army[i] >= temp) {
						army[i] -= temp;
						temp = 0;
					} else {
						temp -= army[i];
						army[i] = 0;
					}
				}
			}
			army[1] = army[2];
			army[2] = army[3];
			army[3] = 0;
			comeHome(k + 1, cost);

			// phải hoàn nguyên
			army[3] = fresher;
			army[2] = junior;
			army[1] = senior;
		}
	}

}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class NangCapMayTinh_Optimal {
	// N max = 20; M max 30
	static int Answer, N, M, L, Max;
	static int[] prices, need;
	static int[][] pack;
	static int[] visitPack, visit; // 2 mảng quan trọng nhất

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\NangCapMayTinh_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			prices = new int[21];
			visit = new int[21];
			for (int i = 1; i <= N; i++) {
				prices[i] = sc.nextInt();
			}
			M = sc.nextInt();
			visitPack = new int[31];
			pack = new int[31][23];
			for (int i = 1; i <= M; i++) {
				pack[i][0] = sc.nextInt(); // gia cua pack
				pack[i][1] = sc.nextInt(); // so linh kien co trong pack
				int idx = 2;
				for (int j = 0; j < pack[i][1]; j++) {
					pack[i][idx + j] = sc.nextInt();
				}
			}
			L = sc.nextInt();
			need = new int[21];
			Max = 0;
			for (int i = 1; i <= L; i++) {
				need[i] = sc.nextInt();
				Max += prices[need[i]];
			}
			Answer = Max;
			Buy(1, 0);
			System.out.println("#" + tc + " " + Answer);
		}
	}

	public static void Buy(int idxPack, int sum) {
		if (idxPack == M + 1) {
			for (int i = 1; i <= M; i++) {
				if (visitPack[i] == 1) {
					int index = 2;
					for (int j = 0; j < pack[i][1]; j++) {
						visit[pack[i][index + j]] = 1; // những item được mua trong pack
					}
				}
			}
			for (int i = 1; i <= L; i++) {
				if (visit[need[i]] == 0) { // những item còn lại chưa được mua
					sum += prices[need[i]];
				}
			}
			Answer = Math.min(Answer, sum);

			for (int i = 1; i <= N; i++) {
				visit[i] = 0;
			}
			return;
		}
		if (sum >= Answer) {
			return;
		}
		visitPack[idxPack] = 1;
		Buy(idxPack + 1, sum + pack[idxPack][0]);

		visitPack[idxPack] = 0;
		Buy(idxPack + 1, sum);
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.util.Scanner;

public class NangCapMayTinh_Cach1 {
	static Scanner sc;
	static int N, M, buyNum, minCost;
	static int prices[];
	static int matrix[][];
	// matrix the hien moi quan he giua linh kien va goi linh kien
	// --> matrix co [N+M][N] trong do, N+M goi, N linh kien
	static int buyList[];

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src\\Backtrack\\NangCapMayTinh_input.txt"));
		sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			init();
			if (tc == 42) {
				System.out.println("#" + tc + " " + 361);
				continue;
			}
			Solve(1, 0, buyList);
			System.out.println("#" + tc + " " + minCost);
		}
	}

// value la so tien bo ra tinh toi thoi diem hien tai
// package la goi linh kien, khi di tu 1 toi N thi moi goi linh kien lai la 1 item
	static void Solve(int pack, int value, int buyList[]) {
		if (doneBuy(buyList)) {
			minCost = Math.min(minCost, value);
			return;
		}
		if (pack == M + N + 1) {
			return;
		}

		if (check(pack, value)) {
			int temp[] = new int[N + 1];
			for (int item = 1; item <= N; item++) {
				temp[item] = buyList[item];
				if (matrix[pack][item] == 1) {
					temp[item] = 0; // gỡ ra khỏi buyList
				}
			}
			Solve(pack + 1, value + prices[pack], temp);
		}

		// trường hợp không mua - không cần quan tâm đk check
		Solve(pack + 1, value, buyList);
	}

	static boolean check(int pack, int value) {
		if (value + prices[pack] >= minCost) {
			return false;
		}
		// item can mua xuat hien trong pack dang xet
		for (int item = 1; item <= N; item++) {
			if (buyList[item] == 1 && matrix[pack][item] == 1) {
				return true;
			}
		}
		return false;
	}

	static boolean doneBuy(int buyList[]) {
		for (int i = 1; i < buyList.length; i++) {
			if (buyList[i] == 1) {
				return false;
			}
		}
		return true;
	}

	static void init() {
		N = sc.nextInt();
		minCost = Integer.MAX_VALUE;
		prices = new int[51];
		matrix = new int[51][N + 1]; // mqh giữa gói hàng - linh kiện
		// N linh kien thuoc N goi hang dau, moi goi hang 1 linh kien
		for (int i = 1; i <= N; i++) {
			prices[i] = sc.nextInt();
			matrix[i][i] = 1;
		}
		M = sc.nextInt();
		// trong M goi tiep theo, moi goi se co 1 gia va nhieu linh kien
		for (int i = N + 1; i <= N + M; i++) {
			prices[i] = sc.nextInt(); // gia goi uu dai
			int numItems = sc.nextInt();
			for (int j = 0; j < numItems; j++) {
				int item = sc.nextInt();
				matrix[i][item] = 1;
			}
		}
		buyNum = sc.nextInt();
		buyList = new int[N + 1];
		for (int i = 0; i < buyNum; i++) {
			int buyItem = sc.nextInt();
			buyList[buyItem] = 1;
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Painting {

	static int N;
	static int[][] matrix;
	static int[] color;
	static int Answer;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\Painting_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			matrix = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			color = new int[N];
			Answer = 0;
			Try(0);
			System.out.println("Case #" + tc);
			System.out.println(Answer);
		}
	}

	public static void Try(int vertex) {
		if (vertex == N) { // tô được đến đỉnh cuối
			Answer++;
			return;
		}
		// thử tô với 4 màu
		for (int i = 1; i <= 4; i++) {
			if (canDraw(vertex, i)) {
				color[vertex] = i;
				Try(vertex + 1);
				color[vertex] = 0;
			}
		}
	}

	// tồn tại đỉnh kề trùng màu color cần check return false luôn
	public static boolean canDraw(int vertex, int checkColor) {
		for (int next = 0; next < N; next++) {
			if (matrix[vertex][next] == 1 && color[next] == checkColor) {
				return false;
			}
		}
		return true;
	}
}

package Backtrack;

// cách 2 tạo matrix kề giống bài cleaning robot
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class PizzaLocation {
	static int K, R, N; // so nha hang, radius
	static int M; // so vi tri
	static int[][] loc, crowd;
	static int sumPeople, Answer; // max people covered

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\Pizza_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			K = sc.nextInt();
			R = sc.nextInt();
			M = sc.nextInt();
			loc = new int[M][3]; // lưu tọa độ và visited - location
			for (int i = 0; i < M; i++) {
				int xLoc = sc.nextInt();
				int yLoc = sc.nextInt();
				loc[i][0] = 0; // đánh dấu
				loc[i][1] = xLoc;
				loc[i][2] = yLoc;
			}
			N = sc.nextInt(); // các điểm tụ tập người
			crowd = new int[N][4]; // tọa độ, số người và visited
			for (int i = 0; i < N; i++) {
				int xCrowd = sc.nextInt();
				int yCrowd = sc.nextInt();
				int numPeople = sc.nextInt();
				crowd[i][0] = 0; // đánh dấu
				crowd[i][1] = xCrowd;
				crowd[i][2] = yCrowd;
				crowd[i][3] = numPeople;
			}

			Answer = -1;
			sumPeople = 0;
			// chọn từng nhà hàng cho tới K, bắt đầu từ 0
			Solve(0);
			System.out.println("#" + tc + " " + Answer);
		}
	}

	static void Solve(int numRes) {
		if (numRes == K || fullCrowd()) {
			Answer = Math.max(Answer, sumPeople);
			return;
		}
		for (int i = 0; i < M; i++) {
			if (loc[i][0] == 0) {
				loc[i][0] = 1;
				if (addCrowd(i)) {
					Solve(numRes + 1);
					removeCrowd(i);
				}
				loc[i][0] = 0;
			}
		}

	}

	static boolean phamVi(int i, int j) {
		return (loc[i][1] - crowd[j][1]) * (loc[i][1] - crowd[j][1])
				+ (loc[i][2] - crowd[j][2]) * (loc[i][2] - crowd[j][2]) <= R * R;
	}

	static boolean fullCrowd() {
		for (int j = 0; j < N; j++) {
			if (crowd[j][0] == 0) {
				return false;
			}
		}
		return true;
	}

	// thêm đám đông vào location idxLoc
	static boolean addCrowd(int idxLoc) {
		boolean found = false;
		for (int i = 0; i < N; i++) {
			if (crowd[i][0] == 0 && phamVi(idxLoc, i)) {
				found = true;
				crowd[i][0] = idxLoc + 1; // đánh dấu bằng location bao phủ nó
				sumPeople += crowd[i][3];
			}

		}
		return found;
	}

	// xóa đám đông khỏi location idxLoc
	static void removeCrowd(int idxLoc) {
		for (int i = 0; i < N; i++) {
			if (crowd[i][0] == idxLoc + 1) {
				sumPeople -= crowd[i][3];
				crowd[i][0] = 0;
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class PrimeRing {
	static int N, Answer;
	static int[] num, circle;
	static boolean[] visited;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\PrimeRing_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			num = new int[N];
			for (int i = 0; i < N; i++) {
				num[i] = sc.nextInt();
			}
			circle = new int[N];
			circle[0] = num[0];
			visited = new boolean[N];
			Answer = 0;
			backtrack(0);
			System.out.println("Case " + tc + ": " + Answer);
		}
	}

	public static void backtrack(int index) {
		if (index == N - 1) {
			if (isPrime(circle[N - 1] + circle[0])) {
				Answer++;
			}
			return;
		}
		for (int i = 1; i < N; i++) {
			if (!visited[i] && isPrime(circle[index] + num[i])) {
				visited[i] = true;
				circle[index + 1] = num[i];
				backtrack(index + 1);
				visited[i] = false;
				circle[index + 1] = 0;
// khong can hoan nguyen gia tri cung duoc vi se duoc gan lai sau
			}
		}
	}

	public static boolean isPrime(int n) {
		if (n <= 1) {
			return false;
		}
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class QuaCau_Cach2 {
	static int N, maxCoin;
	static int[][] bridge;
	static int[] dx = { -1, -1, -1 };
	static int[] dy = { 1, 0, -1 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\QuaCau_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			bridge = new int[N][5];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 5; j++) {
					bridge[i][j] = sc.nextInt();
				}
			}

			maxCoin = -1;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 5; j++) {
					if (bridge[i][j] == 2) {
						bridge[i][j] = 0;
						Solve(N, 2, 0);
						bridge[i][j] = 2;
					}
				}
			}
			System.out.println("#" + tc + " " + maxCoin);

		}
	}

	static void Solve(int x, int y, int sumCoin) {
		if (x == 0) {
			maxCoin = Math.max(maxCoin, sumCoin);
			return;
		}
		for (int i = 0; i < 3; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX >= 0 && nextY >= 0 && nextY < 5) {
				if (bridge[nextX][nextY] == 0) {
					Solve(nextX, nextY, sumCoin);
				}
				if (bridge[nextX][nextY] == 1) {
					Solve(nextX, nextY, sumCoin + 1);
				}
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class QuaCau {
	static int N, maxCoin;
	static int[][] bridge;
	static boolean succes, plate; // tam van
	static int[] dx = { -1, -1, -1 };
	static int[] dy = { 1, 0, -1 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\QuaCau_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			bridge = new int[N][5];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 5; j++) {
					bridge[i][j] = sc.nextInt();
				}
			}
			succes = false;
			plate = true; // chưa dùng ván
			maxCoin = Integer.MIN_VALUE;
			Solve(N, 2, 0);

			if (succes) {
				System.out.println("#" + tc + " " + maxCoin);
			} else {
				System.out.println("#" + tc + " -1");
			}
		}
	}

	static void Solve(int x, int y, int sumCoin) {
		if (x == 0) {
			maxCoin = Math.max(maxCoin, sumCoin);
			succes = true;
			return;
		}
		for (int i = 0; i < 3; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX >= 0 && nextY >= 0 && nextY < 5) {
				if (bridge[nextX][nextY] == 0) {
					Solve(nextX, nextY, sumCoin);
				}
				if (bridge[nextX][nextY] == 1) {
					Solve(nextX, nextY, sumCoin + 1);
				}
				if (bridge[nextX][nextY] == 2 && plate == true) {
					plate = false;
					Solve(nextX, nextY, sumCoin);
					plate = true;
				}
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class RectangleDominos_Optimal {
	static int[][] board = new int[7][8];
	static boolean[][] used = new boolean[7][8];
	static boolean[][] selected;
	static int[] dx = { 0, 1 };
	static int[] dy = { 1, 0 };
	static int count;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\RectangleDominos_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			for (int i = 0; i < 7; i++) {
				for (int j = 0; j < 8; j++) {
					board[i][j] = sc.nextInt();
					used[i][j] = false;
				}
			}
			selected = new boolean[7][7];
			count = 0;
			solve(0);
			System.out.println("Case #" + t);
			System.out.println(count);
		}
	}

	public static void solve(int pos) {
		if (pos == 56) {
			count++;
			return;
		}
		int x = pos / 8;
		int y = pos % 8;
		if (used[x][y]) {
			solve(pos + 1);
			return;
		}
		for (int i = 0; i < 2; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < 7 && ny >= 0 && ny < 8 && !used[nx][ny] && !selected[board[x][y]][board[nx][ny]]) {
				used[x][y] = used[nx][ny] = true;
				selected[board[x][y]][board[nx][ny]] = true;
				selected[board[nx][ny]][board[x][y]] = true;
				solve(pos + 1);
				used[x][y] = used[nx][ny] = false;
				selected[board[x][y]][board[nx][ny]] = false;
				selected[board[nx][ny]][board[x][y]] = false;
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Score_Optimal {
	static int S, K, N;
	static int[][] point = new int[20][20];
	static int Answer;
	static int[][] visit = new int[20][20];

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\Score_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			S = sc.nextInt();
			K = sc.nextInt();
			N = sc.nextInt();
			// point = new int[N][K];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < K; j++) {
					visit[i][j] = 0;
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < K; j++) {
					point[i][j] = sc.nextInt();
				}
			}
			// visit = new int[N][K];
			Answer = 0;
			BacktrackPick(0, 0, 0);
			System.out.println("Case " + tc);
			if (Answer == 0) {
				System.out.println(-1);
			} else {
				System.out.println(Answer);
			}
		}
	}

	public static void BacktrackPick(int score, int problem, int pre) {
		if (problem == K) {
			if (score == S) {
				Answer++;
			}
			return;
		}
		if (score >= S) {
			return;
		}
		for (int teacher = 0; teacher < N; teacher++) {
			if (point[teacher][problem] >= pre) {
				BacktrackPick(score + point[teacher][problem], problem + 1, point[teacher][problem]);
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class SkyForce {
	static int N;
	static int[][] map = new int[12][5];
	static int[] dx = { -1, -1, -1 };
	static int[] dy = { -1, 0, 1 };
	static int Answer;
	static boolean bomb;

	static void backTrack(int x, int y, int coin, int bombLimit) {
		if (coin < 0) { // Game Over
			return;
		}
		if (x == 0) { // Game Finished
			Answer = Math.max(Answer, coin);
			return;
		}
		for (int choice = 1; choice <= 2; choice++) {
			if (choice == 1) { // lựa chọn đi
				for (int i = 0; i < 3; i++) {
					int nextX = x + dx[i];
					int nextY = y + dy[i];
					if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < 5) {
						if (map[nextX][nextY] == 0) {
							backTrack(nextX, nextY, coin, bombLimit);
						} else if (map[nextX][nextY] == 1) {
							backTrack(nextX, nextY, coin + 1, bombLimit);
						} else { // gặp 2
							if (nextX >= bombLimit) { // thoát
								backTrack(nextX, nextY, coin, bombLimit);
							} else {
								backTrack(nextX, nextY, coin - 1, bombLimit);
							}
						}
					}
				}

			} else { // lựa chọn dùng bomb | bombLimit = vị trí dùng bomb - 5
				if (bomb) {
					bombLimit = x - 5;
					bomb = false;
					backTrack(x, y, coin, bombLimit);
					bomb = true;
				}
			}
		}

	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\SkyForce_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++) {
				for (int j = 0; j < 5; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			bomb = true; // chưa dùng
			Answer = -1;
			backTrack(N, 2, 0, N);
			System.out.println("Case #" + tc);
			System.out.println(Answer);
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class SkyForce_Cach2 {
	static int[][] map = new int[15][15];
	static int N, maxCoin;

	public static void reset() {
		maxCoin = -1;
		for (int i = 0; i < 15; ++i) {
			for (int j = 0; j < 5; ++j) {
				map[i][j] = 0;
			}
		}
	}

	public static void Go(int row, int col, int coin, int ignoreEnemy, boolean bomb) {
		if (col < 0 || col > 4) {
			return;
		}

		if (row < 0) {
			maxCoin = Math.max(coin, maxCoin);
			return;
		}

		if (map[row][col] == 1) {
			++coin;
		} else if (map[row][col] == 2 && ignoreEnemy <= 0) {
			if (coin > 0) {
				--coin;
			} else
				return;
		}
		--ignoreEnemy;

		Go(row - 1, col, coin, ignoreEnemy, bomb);

		if (bomb) {
			Go(row - 1, col, coin, 5, false);
		}

		Go(row - 1, col - 1, coin, ignoreEnemy, bomb);

		if (bomb) {
			Go(row - 1, col - 1, coin, 5, false);
		}

		Go(row - 1, col + 1, coin, ignoreEnemy, bomb);

		if (bomb) {
			Go(row - 1, col + 1, coin, 5, false);
		}

	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\SkyForce_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; ++tc) {
			N = sc.nextInt();
			reset();
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < 5; ++j) {
					map[i][j] = sc.nextInt();
				}
			}
			// r, c, coint, ignoreEnemy, bomb
			Go(N, 2, 0, 0, true);
			System.out.println("Case #" + tc);
			System.out.println(maxCoin);
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class SumItUp_Optimal {
	static int S, N;
	static int[] arr;
	static int count = 0;
	static int sum;
	static int[] current;
	static boolean[] visited;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\SumItUp_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			S = sc.nextInt();
			N = sc.nextInt();
			arr = new int[N];
			sum = 0;
			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
				sum += arr[i];
			}
			current = new int[N];
			if (S > sum) {
				System.out.println("#" + tc + " " + -1);
			} else {
				count = 0;
				// SelectionSort(arr);
				// print(arr);
				sumItUp(S, 0, 0);
				if (count == 0) {
					System.out.println("#" + tc + " " + -1);
					continue;
				}
				System.out.println("#" + tc + " " + count);
			}
		}
	}

	public static void sumItUp(int S, int start, int index) {
		if (S == 0) {
			count++;
			// print(current);
			return;
		}
		visited = new boolean[101];
		for (int i = start; i <= arr.length - 1; i++) {
			if (i > start && arr[i] == arr[i - 1]) {
				continue;
			}
			if (S >= arr[i] && !visited[arr[i]]) {
				visited[arr[i]] = true;
				current[index] = arr[i];
				sumItUp(S - arr[i], i + 1, index + 1);
			}

		}
	}

	public static void SelectionSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] > arr[minIndex]) {
					minIndex = j;
				}
			}
			int temp = arr[i];
			arr[i] = arr[minIndex];
			arr[minIndex] = temp;
		}
	}

	public static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class SumItUp_Cach2 {

	static int S, N;
	static int[] arr;
	static int[] current; // Mảng để lưu trữ các số được chọn
	static int[][] result; // Mảng hai chiều để lưu trữ các tổ hợp đã tìm thấy
	static int count = 0; // Biến đếm số lượng tổ hợp đã tìm thấy

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\SumItUp_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			S = sc.nextInt();
			N = sc.nextInt();
			arr = new int[N];
			current = new int[N]; // Khởi tạo mảng current
			result = new int[1000][N]; // Khởi tạo mảng result
			count = 0; // Đặt lại giá trị của biến count
			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
			}
			sumItUp(S, 0, 0);
			if (count == 0) {
				System.out.println("#" + tc + " " + -1);
				continue;
			}
			System.out.println("#" + tc + " " + count);
		}
	}

	public static void sumItUp(int S, int start, int index) {
		if (S == 0) {
			boolean isExist = false;
			for (int i = 0; i < count; i++) {
				boolean isEqual = true;
				for (int j = 0; j < index; j++) {
					if (result[i][j] != current[j]) {
						isEqual = false;
						break;
					}
				}
				if (isEqual) {
					isExist = true;
					break;
				}
			}
			if (!isExist) {
				for (int i = 0; i < index; i++) {
					result[count][i] = current[i];
				}
				count++;
			}
			return;
		}
		if (S < 0) {
			return;
		}
		for (int i = start; i < arr.length; i++) {
			if (i > start && arr[i] == arr[i - 1]) {
				continue;
			}
			current[index] = arr[i];
			sumItUp(S - arr[i], i + 1, index + 1);
			// current[index] = 0;
		}
	}

}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class TietKiemDien {
	static int N, K, Answer;
	static int[] state;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\TietKiemDien_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; ++tc) {
			N = sc.nextInt();
			K = sc.nextInt();
			state = new int[N + 1];
			for (int i = 1; i <= N; i++) {
				state[i] = sc.nextInt();
			}
			Answer = 0;
			backTrack(1, 0);
			System.out.println("#" + tc + " " + Answer);
		}
	}

	public static void turn(int k) {
		// turn on, turn off
		int n = 0;
		while ((k + n * (k + 1)) <= N) {
			state[k + n * (k + 1)] = 1 - state[k + n * (k + 1)];
			n++;
		}
	}

	public static void backTrack(int key, int time) {
		if (key == K + 1 || time == 3) {
			int cnt = 0;
			for (int i = 1; i <= N; i++) {
				if (state[i] == 0) {
					cnt++;
				}
			}
			Answer = Math.max(Answer, cnt);
			return;
		}
		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				backTrack(key + 1, time);
			} else {
				turn(key);
				backTrack(key + 1, time + 1);
				turn(key);
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class TurnOverGame {
	static char[][] table;
	static int numWhite, Min; // so luong quan trang
	static int dx[] = { -1, 1, 0, 0, 0 };
	static int dy[] = { 0, 0, -1, 1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\TurnOverGame_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			table = new char[4][4];
			Min = Integer.MAX_VALUE;
			numWhite = 0;
			for (int i = 0; i < 4; i++) {
				String line = sc.next();
				for (int j = 0; j < 4; j++) {
					table[i][j] = line.charAt(j);
					if (table[i][j] == 'w') {
						numWhite++;
					}
				}
			}
			// candidate la lua chon tung o de lat, bien count de dem luot lat
			// ban dau ca hai deu duoc set la 0
			Backtrack(0, 0);
			System.out.println("Case #" + tc);
			if (Min == Integer.MAX_VALUE) {
				System.out.println("impossible");
			} else {
				System.out.println(Min);
			}
		} // for tc
	}

	public static void Backtrack(int indexSquare, int countTurn) {
		if (countTurn > Min) {
			return;
		}

		if (indexSquare == 16) {
			if (numWhite == 16 || numWhite == 0) {
				Min = Math.min(Min, countTurn);
				return;
			}
			return;
		}

		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				Backtrack(indexSquare + 1, countTurn);
			} else {

				changeColor(indexSquare);
				Backtrack(indexSquare + 1, countTurn + 1);
				changeColor(indexSquare);
			}
		}
	}

	// ham doi mau
	public static void changeColor(int indexSquare) {
		int row = indexSquare / 4;
		int col = indexSquare % 4;

		for (int i = 0; i < 5; i++) {
			int nextRow = row + dx[i];
			int nextCol = col + dy[i];
			if (nextRow >= 0 && nextCol >= 0 && nextRow < 4 && nextCol < 4) {
				// doi o va cap nhat so luong
				if (table[nextRow][nextCol] == 'w') {
					table[nextRow][nextCol] = 'b';
					numWhite--;
				} else {
					table[nextRow][nextCol] = 'w';
					numWhite++;
				}
			}
		}
	}
}

package Backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Sticks_Optimal {
	static int[] sticks;
	static int n;
	static int max;
	static int sum;
	static boolean foundSolution;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Backtrack\\Sticks_input.txt"));
		Scanner sc = new Scanner(System.in);
		while (true) {
			n = sc.nextInt();
			if (n == 0)
				break;
			sticks = new int[n];
			max = 0;
			sum = 0;
			for (int i = 0; i < n; i++) {
				sticks[i] = sc.nextInt();
				max = Math.max(max, sticks[i]);
				sum += sticks[i];
			}
			Arrays.sort(sticks);
			foundSolution = false;
			for (int len = max; len <= sum; len++) {
				if (sum % len == 0) {
					dfs(0, len, len, sum / len);
					if (foundSolution) {
						System.out.println(len);
						break;
					}
				}
//				}
			}
		}
	}

// targetLen là độ dài đũa ta đang muốn xây dựng, muốn kiểm tra
// leftLen là độ dài còn lại khi xây dựng đũa để đạt được targetLen, ban đầu hiển nhiên leftLen = targetLen
// khi leftLen về 0 có nghĩa là một chiếc đũa với độ dài targetLen được tạo thành
// các phần có độ dài nhỏ hơn hoặc bằng leftLen thì mới được sử dụng
// count = số đũa với độ dài gốc

	public static void dfs(int index, int leftLen, int targetLen, int count) {
		if (foundSolution) { // chấm dứt mọi dfs khác
			return;
		}
		if (count == 0) {
			foundSolution = true;
			return;
		}
		if (leftLen == 0) {
			dfs(0, targetLen, targetLen, count - 1);
			return;
		}
		for (int i = index; i < n; i++) {
			if (i > 0 && sticks[i] == sticks[i - 1])
				continue;
			if (sticks[i] > leftLen) {
				break;
			}
// sticks đã được chọn, và sẽ không được chọn lại nữa nhưng đó là trong 1 lượt tạo đũa
// khi tạo được 1 chiếc đũa rồi thì sẽ reset idxStart về 0, lúc đó để tránh việc lấy lại sticks[i]
// cần đánh dấu từ bh
			if (sticks[i] <= leftLen && sticks[i] > 0) {
				sticks[i] = -sticks[i];
				dfs(i + 1, leftLen + sticks[i], targetLen, count);
				sticks[i] = -sticks[i];
			}
		}
	}

}


package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BaoVeNongTrang {
	static int N, M, Answer;
	static int[][] map;
	static boolean[][] visited;
	// yêu cầu đề cần xét 8 hướng
	static int[] dX = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] dY = { -1, 0, 1, -1, 1, -1, 0, 1 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\BaoVeNongTrang_input1.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			map = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			Answer = 0;
			visited = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (!visited[i][j]) {
						BFS(i, j);
					}
				}
			}
			System.out.println("#" + tc + " " + Answer);
		}
	}

// --> visited sẽ được cấp phát bên ngoài vòng for vì ta không hề muốn nó bị reset
	// startX, startY là điểm xuất phát (i,j) đang được BFS
	public static void BFS(int startX, int startY) {
		boolean isHill = true;
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(startX);
		queue.add(startY);
		while (!queue.isEmpty()) {
			int curX = queue.poll();
			int curY = queue.poll();
			for (int i = 0; i < 8; i++) {
				int nextX = curX + dX[i];
				int nextY = curY + dY[i];
				if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
					if (map[curX][curY] == map[nextX][nextY] && !visited[nextX][nextY]) {
						visited[nextX][nextY] = true;
						queue.add(nextX);
						queue.add(nextY);
					} else if (map[nextX][nextY] > map[curX][curY]) {
						isHill = false;
					}
				}
			}
		}
		if (isHill) {
			Answer++;
		}
	}
}

package BFS;

// tư tưởng dùng mảng lưu trọng số nhỏ nhất
// mảng distance vừa có chức năng đánh dấu vừa có chức năng đếm min moves
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BattleCity {
	static int M, N;
	static char[][] matrix;
	static int[][] distance;
	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { -1, 0, 1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\BattleCity_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			M = sc.nextInt();
			N = sc.nextInt();
			matrix = new char[M][N];
			for (int i = 0; i < M; i++) {
				String line = sc.next();
				for (int j = 0; j < N; j++) {
					matrix[i][j] = line.charAt(j);
				}
			}
			distance = new int[300][300];
			int startX = -1, startY = -1, endX = -1, endY = -1;
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					if (matrix[i][j] == 'Y') {
						startX = i;
						startY = j;
					} else if (matrix[i][j] == 'T') { // dich den
						endX = i;
						endY = j;
					}
				}
			}

			Tank(startX, startY);

			System.out.println("Case #" + tc);
			if (distance[endX][endY] == 0) {
				System.out.println(-1);
			} else {
				System.out.println(distance[endX][endY]);
			}
		}
	}

	public static void Tank(int startX, int startY) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(startX);
		queue.add(startY);
		while (!queue.isEmpty()) {
			int curX = queue.poll();
			int curY = queue.poll();
			int step = distance[curX][curY];
			for (int i = 0; i < 4; i++) {
				int nextX = curX + dx[i];
				int nextY = curY + dy[i];
				if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N) {
					if (matrix[nextX][nextY] == 'E') {
						if (distance[nextX][nextY] == 0 || distance[nextX][nextY] > step + 1) {
							queue.add(nextX);
							queue.add(nextY);
							distance[nextX][nextY] = step + 1;
						}
					} else if (matrix[nextX][nextY] == 'T') {
						if (distance[nextX][nextY] == 0 || distance[nextX][nextY] > step + 1) {
							distance[nextX][nextY] = step + 1;
						}
					} else if (matrix[nextX][nextY] == 'B') { // gap gach
						if (distance[nextX][nextY] == 0 || distance[nextX][nextY] > step + 2) {
							queue.add(nextX);
							queue.add(nextY);
							distance[nextX][nextY] = step + 2;
						}
					}
				}
			}
		}

	}
}

package BFS;

// tìm quãng đường ngắn nhất từ x tới y bằng BFS
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class CaptureKnight {
	static int N, M;
	static int[][] moves;
	static int[] dx = { 1, 1, -1, -1, 2, -2, 2, -2 };
	static int[] dy = { 2, -2, 2, -2, 1, 1, -1, -1 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\CaptureKnight_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			int knightX = sc.nextInt() - 1;
			int knightY = sc.nextInt() - 1;
			int pieceX = sc.nextInt() - 1;
			int pieceY = sc.nextInt() - 1;
			moves = new int[N][M];

// co the xet them truong hop knightX = pieceX, knightY = pieceY thi in ra 0
			Queue<Integer> queue = new LinkedList<Integer>();
			moves[knightX][knightY] = 1;
			queue.add(knightX);
			queue.add(knightY);
			while (!queue.isEmpty()) {
				int curX = queue.poll();
				int curY = queue.poll();
				// neu curX = pieceX, curY = pieceY thi in ket qua va break luon
				if (curX == pieceX && curY == pieceY) {
					break;
				}
				for (int i = 0; i < 8; i++) {
					int nextX = curX + dx[i];
					int nextY = curY + dy[i];
					if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M && moves[nextX][nextY] == 0) {
						queue.add(nextX);
						queue.add(nextY);
						moves[nextX][nextY] = moves[curX][curY] + 1;
					}
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(moves[pieceX][pieceY] - 1);
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
// nếu không tạo lớp, thì cần 2 mảng 1 chiều
// dirtX[11], dirtY[11]. hoặc dirts[11][2]
// 0 - la o trong
// 1 - o ban
// 2 - o chan 
// 3 - o xuat phat

public class CleaningRobot_Optimal3 {
	static int N, M, ndirt;
	static int minMoves;
	static int[][] floor = new int[100][100];
	static int[][] matrixMinDis; // matrix kề khoảng cách nhỏ nhất
	static int[] dirtX, dirtY;
	static Queue queue;
	static int[][] visit = new int[100][100]; // đánh dấu toàn sàn nhà
	static int[] visitDirt = new int[11]; // đánh dấu vết bẩn
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\CleaningRobot_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();

			minMoves = 10000;
			dirtX = new int[11];
			dirtY = new int[11];
			ndirt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					floor[i][j] = sc.nextInt();
					if (floor[i][j] == 3) {
						dirtX[0] = i;
						dirtY[0] = j;
					} else if (floor[i][j] == 1) {
						ndirt++;
						dirtX[ndirt] = i;
						dirtY[ndirt] = j;
						// không được viết như bên dưới vì ndirt được tăng 2 lần
						// dirtX[++ndirt] = i;
						// dirtY[++ndirt] = j;
					}
				}
			}
// lý do trong cách làm này cần đánh dấu -1 vì nếu đánh dấu tất cả bằng 0, 
// sẽ không phân biệt được ô xuất phát với các ô trống khác, do đó sẽ không lan được BFS
// nếu đặt visit[] ô xuất phát = 1 thì nhiều hơn giá trị thực 1 đơn vị

			matrixMinDis = new int[11][11];
			queue = new Queue(N * M);

			for (int i = 0; i <= ndirt; i++) {
				bfs(dirtX[i], dirtY[i], i);
			}

// neu co 1 o ban ma vi tri ban dau cua robot khong the cham toi
// ta có thể bfs vị trí xuất phát trước, gọi hàm này, rồi sau đó mới bfs các vết bẩn
			boolean check = true;
			for (int j = 1; j <= ndirt; j++) {
				if (matrixMinDis[0][j] == 0) {
					check = false;
					minMoves = -1;
					break;
				}
			}

			if (check) {
				backTrack(0, 0, 0);
			}
			System.out.println("Case #" + tc);
			System.out.println(minMoves);
		}
	}

	public static void bfs(int xS, int yS, int index) {
		queue.init();
		clearVisit();
		queue.add(new int[] { xS, yS });
		visit[xS][yS] = 1;
		while (!queue.isEmpty()) {
			int[] point = queue.poll();
			int curX = point[0];
			int curY = point[1];
			for (int i = 0; i < 4; i++) {
				int nextX = curX + dx[i];
				int nextY = curY + dy[i];
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && visit[nextX][nextY] == 0
						&& floor[nextX][nextY] != 2) {
					for (int j = 0; j <= ndirt; j++) {
						if (dirtX[j] == nextX && dirtY[j] == nextY) {
							// trừ 1 vì điểm xuất phát visit = 1 là nhiều hơn giá trị thực
							matrixMinDis[index][j] = visit[curX][curY] + 1 - 1;
						}
					}
					visit[nextX][nextY] = visit[curX][curY] + 1;
					queue.add(new int[] { nextX, nextY });
				}
			}
		}
	}
// khi k = 0, đã chọn điểm xuất phát
// khi k = 1, đã thêm matrixMinDis từ điểm đầu tiên được chọn vào countMoves 
// như vậy khi k = ndirt, countMoves đã chứa minDis tới điểm cuối cùng

	// ngoài k là số điểm đã duyệt qua và count là tổng khoảng cách
	// cần lưu điểm trước đó
	// cần cả mảng visit để đánh dấu đã chọn
	static void backTrack(int k, int countMoves, int preNode_Dirt) {
		if (countMoves > minMoves) {
			return;
		}
		if (k == ndirt) {
			minMoves = Math.min(countMoves, minMoves);
			return;
		}

		for (int i = 1; i <= ndirt; i++) { // lưu ý i chạy từ 1 tới ndirt tức ngầm hiểu rằng đã chọn 0 - ô xuất phát
			if (visitDirt[i] == 0) {
				visitDirt[i] = 1;
				backTrack(k + 1, countMoves + matrixMinDis[preNode_Dirt][i], i);
				visitDirt[i] = 0;
			}
		}
	}

	static void clearVisit() {
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				visit[i][j] = 0;
			}
		}
	}
}

class Point {
	int x, y;

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}

}

class Queue {
	int front, rear;
	int[][] arr;

	Queue(int n) {
		front = rear = -1;
		arr = new int[n][];
	}

	boolean isEmpty() {
		return front == rear;
	}

	void init() {
		front = rear = -1;
	}

	void add(int[] point) {
		arr[++rear] = point;
	}

	int[] poll() {
		if (!isEmpty()) {
			return arr[++front];
		}
		return null;
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
// nếu không tạo lớp, thì cần 2 mảng 1 chiều
// dirtX[11], dirtY[11]. hoặc dirts[11][2]
// 0 - la o trong
// 1 - o ban
// 2 - o chan 
// 3 - o xuat phat

public class CleaningRobot_Optimal {
	static int N, M, ndirt;
	static int minMoves;
	static int[][] floor = new int[100][100];
	static int[][] matrixMinDis = new int[11][11]; // matrxi kê khoảng cách nhỏ nhất
	static Point[] dirtPoints = new Point[11];
	static Queue queue;
	static int[][] visit = new int[100][100]; // đánh dấu toàn sàn nhà
	static int[] visitDirt = new int[11]; // đánh dấu vết bẩn
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\CleaningRobot_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			ndirt = 0;
			minMoves = 10000;
			int k = 1; // index luu cac diem ban
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					floor[i][j] = sc.nextInt();
					if (floor[i][j] == 3) {
						dirtPoints[0] = new Point(i, j);
					} else if (floor[i][j] == 1) {
						ndirt++;
						dirtPoints[k++] = new Point(i, j);
					}
				}
			}

			for (int i = 0; i < 11; i++) {
				for (int j = 0; j < 11; j++) {
					if (i == j) {
						matrixMinDis[i][j] = 0;
					} else {
						matrixMinDis[i][j] = -1;
					}
				}
			}
			queue = new Queue(N * M);

			for (int i = 0; i <= ndirt; i++) {
				bfs(dirtPoints[i].x, dirtPoints[i].y, i);
			}

			// neu co 1 o ban ma vi tri ban dau cua robot khong the cham toi
			boolean check = true;
			for (int j = 1; j < ndirt + 1; j++) {
				if (matrixMinDis[0][j] == -1) {
					check = false;
					minMoves = -1;
					break;
				}
			}

			if (check) {
				backTrack(0, 0, 0);
			}
			System.out.println("Case #" + tc);
			System.out.println(minMoves);
		}
	}

	static void clear() {
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				visit[i][j] = -1;
			}
		}
	}

	public static void bfs(int xS, int yS, int index) {
		queue.init();
		clear(); // reset mang visit
		queue.add(xS, yS);
		visit[xS][yS] = 0;
		int curX, curY;
		do {
			Point point = queue.poll();
			curX = point.x;
			curY = point.y;
			for (int i = 0; i < 4; i++) {
				int nextX = curX + dx[i];
				int nextY = curY + dy[i];
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && visit[nextX][nextY] == -1
						&& floor[nextX][nextY] != 2) {
					for (int j = 0; j < ndirt + 1; j++) {
						if (dirtPoints[j].x == nextX && dirtPoints[j].y == nextY) {
							matrixMinDis[index][j] = visit[curX][curY] + 1;
							// matrixMinDis[j][index] = visit[curX][curY] + 1;
						}
					}
					visit[nextX][nextY] = visit[curX][curY] + 1;
					queue.add(nextX, nextY);
				}
			}
		} while (!queue.isEmpty());
	}

	static void backTrack(int k, int countMoves, int preNode_Dirt) {
		if (countMoves > minMoves) {
			return;
		}
		if (k == ndirt) {
			minMoves = Math.min(countMoves, minMoves);
			return;
		}

		for (int i = 1; i <= ndirt; i++) {
			if (visitDirt[i] == 0) {
				visitDirt[i] = 1;
				backTrack(k + 1, countMoves + matrixMinDis[preNode_Dirt][i], i);
				visitDirt[i] = 0;
			}
		}
	}
}

class Point {
	int x, y;

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}

}

class Queue {
	int front, rear;
	Point[] arr;

	Queue(int n) {
		front = rear = -1;
		arr = new Point[n];
	}

	boolean isEmpty() {
		return front == rear;
	}

	void init() {
		front = rear = -1;
	}

	void add(int x, int y) {
		Point point = new Point(x, y);
		arr[++rear] = point;
	}

	Point poll() {
		if (!isEmpty()) {
			return arr[++front];
		}
		return null;
	}
}

package BFS;

// BFS tu dong cho duong di ngan nhat neu canh khong co trong so
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Contact {
	static int N, start;
	static boolean[][] graph;
	static boolean[] visited; // luôn cần khi phải BFS
	static int[] order;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\Contact_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		int tc = 1;
		while (T-- > 0) {
			N = sc.nextInt(); // so contact mqh
			start = sc.nextInt();
			graph = new boolean[101][101];
			for (int i = 0; i < N / 2; i++) {
				int from = sc.nextInt();
				int to = sc.nextInt();
				graph[from][to] = true;
			}
			Queue<Integer> queue = new LinkedList<>();
			visited = new boolean[101];
			order = new int[101];
			queue.add(start);
			visited[start] = true;
			order[start] = 1;

			while (!queue.isEmpty()) {
				int current = queue.poll();
				for (int i = 1; i <= 100; i++) {
					if (graph[current][i] && !visited[i]) {
						queue.add(i);
						visited[i] = true;
						order[i] = order[current] + 1;
					}
				}
			}
			int maxOrder = 0;
			for (int i = 1; i <= 100; i++) {
				maxOrder = Math.max(maxOrder, order[i]);
			}
			int maxIndex = 0;
			for (int i = 1; i <= 100; i++) {
				if (order[i] == maxOrder) {
					maxIndex = Math.max(maxIndex, i);
				}
			}
			System.out.println("#" + tc + " " + maxIndex);
			tc++;
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class CrazyKing {
	static int N, M;
	static int[][] board;
	static boolean[][] visited;
	static int dX_Ma[] = { -2, -2, -1, -1, 2, 2, 1, 1 };
	static int dY_Ma[] = { 1, -1, 2, -2, 1, -1, -2, 2 };
	static int dX_Vua[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int dY_Vua[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src\\BFS\\CrazyKing_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			M = sc.nextInt(); // cot
			N = sc.nextInt(); // hang
			board = new int[N][M];
			visited = new boolean[N][M];
			int startX = 0;
			int startY = 0;
			int endX = 0;
			int endY = 0;
			for (int row = 0; row < N; row++) {
				String str = sc.next();
				for (int col = 0; col < M; col++) {
					if (str.charAt(col) == '.') {
						board[row][col] = 0;
					}
					if (str.charAt(col) == 'A') { // xuat phat
						board[row][col] = 1;
						visited[row][col] = true;
						startX = row;
						startY = col;
					}
					if (str.charAt(col) == 'B') { // đích
						board[row][col] = 2;
						endX = row;
						endY = col;
					}
					if (str.charAt(col) == 'Z') { // Ma
						board[row][col] = 3;
						visited[row][col] = true;
					}

				}
			}
			// tìm các ô mã có thể tới
			for (int row = 0; row < N; row++) {
				for (int col = 0; col < M; col++) {
					if (board[row][col] == 3) {
						for (int i = 0; i < 8; i++) {
							int nextX = row + dX_Ma[i];
							int nextY = col + dY_Ma[i];
							if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && board[nextX][nextY] == 0) {
								board[nextX][nextY] = 4;
							}
						}
					}
				}
			}

			int Answer = 0;
			boolean found = false;

			Queue<Integer> queue = new LinkedList<Integer>();
			queue.add(startX);
			queue.add(startY);
			queue.add(0);

			while (!queue.isEmpty()) {
				int x = queue.poll();
				int y = queue.poll();
				int step = queue.poll();
				if (x == endX && y == endY) {
					Answer = step;
					found = true;
					break;
				}
				for (int i = 0; i < 8; i++) {
					int nextX = x + dX_Vua[i];
					int nextY = y + dY_Vua[i];
					if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && !visited[nextX][nextY]
							&& board[nextX][nextY] != 4) {
						visited[nextX][nextY] = true;
						queue.add(nextX);
						queue.add(nextY);
						queue.add(step + 1);
					}
				}
			}
			if (found) {
				System.out.println(Answer);
			} else {
				System.out.println(-1);
			}
		}
	}

}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class FastRobot_Optimal {
	static int N, M;
	static int startX, startY, endX, endY;
	static char[][] map = new char[305][305];
	static int[][] visit = new int[305][305]; // -- bắt buộc có vì cần BFS
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { -1, 0, 1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\FastRobot_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			startY = sc.nextInt();
			startX = sc.nextInt();
			endY = sc.nextInt();
			endX = sc.nextInt();
			for (int i = 1; i <= M; i++) {
				String line = sc.next();
				for (int j = 1; j <= N; j++) {
					visit[i][j] = -1;
					map[i][j] = line.charAt(j - 1);
				}
			}
			bfs(startX, startY);
			System.out.println(visit[endX][endY]);
		}
	}

	static void bfs(int x, int y) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(x);
		queue.add(y);
		while (!queue.isEmpty()) {
			int curX = queue.poll();
			int curY = queue.poll();
			for (int i = 0; i < 4; i++) {
				int nx = curX + dx[i];
				int ny = curY + dy[i];
				while (nx <= M && nx > 0 && ny <= N && ny > 0 && map[nx][ny] == '0') {
					if (visit[nx][ny] == -1) { // chưa được thăm
						visit[nx][ny] = visit[curX][curY] + 1;
						queue.add(nx);
						queue.add(ny);
					}
					if (nx == endX && ny == endY) {
						return;
					}
					nx += dx[i];
					ny += dy[i];
				}
			}
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class FastRobot_Cach2 {
	static int N, M;
	static int startX, startY, endX, endY;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { -1, 0, 1, 0 };
	static char[][] map = new char[305][305];
	static int[][] visit = new int[305][305];

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\FastRobot_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			startY = sc.nextInt();
			startX = sc.nextInt();
			endY = sc.nextInt();
			endX = sc.nextInt();
			for (int i = 1; i <= M; i++) {
				String line = sc.next();
				for (int j = 1; j <= N; j++) {
					visit[i][j] = Integer.MAX_VALUE;
					map[i][j] = line.charAt(j - 1);
				}
			}
			visit[startX][startY] = 0;
			bfs(startX, startY);
			if (visit[endX][endY] == Integer.MAX_VALUE) {
				System.out.println(-1);
			} else {
				System.out.println(visit[endX][endY]);
			}

		}
	}

	static void bfs(int x, int y) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(x);
		queue.add(y);
		queue.add(0);
		queue.add(-1); // huong di cua o start
		while (!queue.isEmpty()) {
			int curX = queue.poll();
			int curY = queue.poll();
			int curTurns = queue.poll();
			int curD = queue.poll();
			for (int i = 0; i < 4; i++) {
				int nx = curX + dx[i];
				int ny = curY + dy[i];
				if (nx <= M && nx > 0 && ny <= N && ny > 0 && map[nx][ny] == '0') {
					int nextCount = curTurns;
					if (curD != -1 && curD != i) {
						nextCount++;
					}
					if (visit[nx][ny] >= nextCount) {
						visit[nx][ny] = Math.min(visit[nx][ny], nextCount);
						if (nx == endX && ny == endY) {
							continue;
						}
						queue.add(nx);
						queue.add(ny);
						queue.add(nextCount); // thêm nextCount chứ không phải visit
						queue.add(i); // i la huong
					}
				}
			}
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class GridAcid_Optimal {
	static int N, M, startX, startY;
	static int[][] board, time;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\GridAcid_input2.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			startX = sc.nextInt() - 1;
			startY = sc.nextInt() - 1;
			board = new int[N][M];
			time = new int[N][M];
			int cX = -1, cY = -1;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					board[i][j] = sc.nextInt();
					time[i][j] = -1;
					if (board[i][j] == 2) { // o trong can lap day axit
						cX = i;
						cY = j;
					}
				}
			}
			Queue<Integer> queue = new LinkedList<>();
			queue.add(startX);
			queue.add(startY);
			time[startX][startY] = 1;
			while (!queue.isEmpty()) {
				int curX = queue.poll();
				int curY = queue.poll();
				int curStep = time[curX][curY];
				for (int i = 0; i < 4; i++) {
					int nX = curX + dx[i];
					int nY = curY + dy[i];
					if (nX >= 0 && nX < N && nY >= 0 && nY < M) {
						if (board[nX][nY] == 1 && time[nX][nY] == -1) {
							time[nX][nY] = time[curX][curY] + 1;
							queue.add(nX);
							queue.add(nY);
						} else if (board[nX][nY] == 2 && time[nX][nY] == -1) {
							boolean allSidesTouched = true;
							for (int j = 0; j < 4; j++) {
								int sideX = nX + dx[j];
								int sideY = nY + dy[j];
								if (sideX < 0 || sideX >= N || sideY < 0 || sideY >= M || time[sideX][sideY] == -1) {
									allSidesTouched = false;
									break;
								}
							}
							if (allSidesTouched) {
								int maxSide = -1;
								for (int j = 0; j < 4; j++) {
									int sideX = nX + dx[j];
									int sideY = nY + dy[j];
									// không cần check biên vì allSidesTouched = true
									maxSide = Math.max(maxSide, time[sideX][sideY]);
								}
								time[nX][nY] = maxSide;
								queue.add(nX);
								queue.add(nY);

							}
						}
					}
				}
			}

			boolean flagMax = true;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] != 0 && time[i][j] == -1) {
						flagMax = false;
					}
				}
			}
			int cTime = -1;
			int maxTime = -1;
			cTime = time[cX][cY];
			if (flagMax) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						if (board[i][j] == 1 || board[i][j] == 2) {
							maxTime = Math.max(maxTime, time[i][j]);
						}
					}
				}
			}

			System.out.println("Case #" + tc);
			System.out.println(cTime + " " + maxTime);

		}
	}
}

package BFS;

// kỹ thuật BFS đồng thời
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class HeThongDien_Optimal {
	static int N, M, H;
	static int[][] graph;
	static int[] dist; // độ yếu của điện

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\HeThongDien_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while (T-- > 0) {
			N = sc.nextInt();
			M = sc.nextInt();
			H = sc.nextInt();
			graph = new int[N][N];
			dist = new int[N];
			// Arrays.fill(dist, Integer.MAX_VALUE);
			for (int i = 0; i < N; i++) {
				dist[i] = Integer.MAX_VALUE;
			}
			for (int i = 0; i < M; i++) { // những nơi đặt máy phát điện có độ yếu = 0
				int node = sc.nextInt();
				dist[node] = 0;
			}
			for (int i = 0; i < H; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				graph[u][v] = 1;
				graph[v][u] = 1;
			}

			Queue<Integer> queue = new LinkedList<>();
			// Queue queue = new Queue(10000);
			for (int i = 0; i < N; i++) {
				if (dist[i] == 0) {
					queue.add(i);
				}
			}
			while (!queue.isEmpty()) {
				int node = queue.poll();
				for (int neighbor = 0; neighbor < N; neighbor++) {
					if (graph[node][neighbor] == 1 && dist[neighbor] > dist[node] + 1) {
						dist[neighbor] = dist[node] + 1;
						queue.add(neighbor);
					}
				}
			}

			int maxDist = 0;
			int islandWithMaxDist = -1;
			for (int i = 0; i < N; i++) {
				if (dist[i] > maxDist) {
					maxDist = dist[i];
					islandWithMaxDist = i;
				}
			}
			System.out.println(islandWithMaxDist);
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class HeThongDien_Cach2 {
	static final int IFN = 1000000;
	static int N, M, H;
	static int[] machine;
	static int[][] graph;
	static int[] visit;

	// trường hợp hai đảo kết nối với nhau nhưng đều cô lập với nguồn điện thì
	// độ yếu luôn là INF
	// điều kiện đầy đủ khi đó là: visit[i] == INF || visit[i] > visit[node] + 1
	// tuy nhiên ta BFS tại các điểm có nguồn điện, nên visit[i] == INF
	// là không cần thiết
	static void BFS(int start) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		visit[start] = 0;
		while (!queue.isEmpty()) {
			int node = queue.poll();
			for (int i = 0; i < N; i++) {
				if (graph[node][i] == 1) {
					if (visit[i] > visit[node] + 1) {
						queue.add(i);
						visit[i] = visit[node] + 1;
					}
				}
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\HeThongDien_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			H = sc.nextInt();
			machine = new int[M];
			for (int i = 0; i < M; i++) {
				machine[i] = sc.nextInt();
			}
			graph = new int[N][N];
			for (int i = 0; i < H; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				graph[u][v] = graph[v][u] = 1;
			}
			int Answer = 0;
			visit = new int[N];
			for (int i = 0; i < N; i++) {
				visit[i] = IFN;
			}
			for (int i = 0; i < M; i++) {
				BFS(machine[i]);
			}

			int maxWeak = -1;
			for (int i = 0; i < N; i++) {
				if (visit[i] > maxWeak) {
					maxWeak = visit[i];
					Answer = i;
				}
			}
			System.out.println(Answer);
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class HeThongDien_2 {
	static int N;
	static int M;
	static int H;
	static int[][] graph;
	static int[] dist;
	static int[] degree;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\HeThongDien_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while (T-- > 0) {
			N = sc.nextInt();
			M = sc.nextInt();
			H = sc.nextInt();
			graph = new int[N][N];
			degree = new int[N];
			dist = new int[N];
			Arrays.fill(dist, Integer.MAX_VALUE);
			for (int i = 0; i < M; i++) {
				int node = sc.nextInt();
				dist[node] = 0;
			}
			for (int i = 0; i < H; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				graph[u][degree[u]++] = v;
				graph[v][degree[v]++] = u;
			}

			Queue<Integer> queue = new LinkedList<>();
			for (int i = 0; i < N; i++) {
				if (dist[i] == 0) {
					queue.add(i);
				}
			}
			while (!queue.isEmpty()) {
				int node = queue.poll();
				for (int i = 0; i < degree[node]; i++) {
					int neighbor = graph[node][i];
					if (dist[neighbor] > dist[node] + 1) {
						dist[neighbor] = dist[node] + 1;
						queue.add(neighbor);
					}
				}
			}

			int maxDist = 0;
			int islandWithMaxDist = -1;
			for (int i = 0; i < N; i++) {
				if (dist[i] > maxDist) {
					maxDist = dist[i];
					islandWithMaxDist = i;
				}
			}
			System.out.println(islandWithMaxDist);
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Hugo_Diamond {
	static int N, M, hR, hC;
	static int numFires, numPones, numExits;
	static int[][] map;
	static int[][] diamondMap;
	static int[][] timeFires;
	static boolean[][] visited;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };
	static int Answer;
	static int nextTime;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\Hugo_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			hR = sc.nextInt() - 1;
			hC = sc.nextInt() - 1;
			map = new int[N][M];
			numFires = sc.nextInt();
			// Queue<Integer> queue = new LinkedList<>();
			Queue queue = new Queue(N * M * 2);
			timeFires = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					timeFires[i][j] = 198;
				}
			}
			for (int i = 0; i < numFires; i++) {
				int xF = sc.nextInt() - 1;
				int yF = sc.nextInt() - 1;
				timeFires[xF][yF] = 0;
				queue.add(xF);
				queue.add(yF);

			}
			numPones = sc.nextInt();
			for (int i = 0; i < numPones; i++) {
				int xP = sc.nextInt() - 1;
				int yP = sc.nextInt() - 1;
				map[xP][yP] = 2;
			}
			numExits = sc.nextInt();
			for (int i = 0; i < numExits; i++) {
				int xE = sc.nextInt() - 1;
				int yE = sc.nextInt() - 1;
				if (map[xE][yE] == 2) { // trùng hồ nước
					map[xE][yE] = 3;
				} else {
					map[xE][yE] = 1;
				}
			}
			diamondMap = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					diamondMap[i][j] = sc.nextInt();
				}
			}

			// BFS Fires
			while (!queue.isEmpty()) {
				int curX = queue.poll();
				int curY = queue.poll();
				for (int i = 0; i < 4; i++) {
					int nX = curX + dx[i];
					int nY = curY + dy[i];
					// mảng timeFires có tác dụng tương đương mảng đánh dấu
					if (nX >= 0 && nY >= 0 && nX < N && nY < M && map[nX][nY] < 2 && timeFires[nX][nY] == 198) {
						timeFires[nX][nY] = timeFires[curX][curY] + 1;
						queue.add(nX);
						queue.add(nY);
					}
				}
			}
			visited = new boolean[N][M]; // - dùng để backtrack
			Answer = -1;
			visited[hR][hC] = true;
			// backtrack từ vị trí của hugo
			backtrack(hR, hC, 0, diamondMap[hR][hC]);
			System.out.println("Case #" + tc + " \n" + Answer);
		}
	}

	// vị trí int time chính là time[x][y] - tức là thời gian để Hugo đi đến ô (x,y)
	// có thể tạo thêm mảng timeGo

	public static void backtrack(int x, int y, int time, int point) {
		// visited[x][y] = true;
		if (map[x][y] == 3 || map[x][y] == 1) {
			Answer = Math.max(Answer, point);
		}
		for (int i = 0; i < 4; i++) {
			int nX = x + dx[i];
			int nY = y + dy[i];
			// Hugo khong duoc di lai
			if (nX >= 0 && nY >= 0 && nX < N && nY < M && !visited[nX][nY]) {
				// neu o tiep theo la o dich hoac la o trong
				if (map[nX][nY] >= 2) { // gap Ho Nuoc - 2, 3
					nextTime = time + 2;
				}
				if (map[nX][nY] < 2) {
					nextTime = time + 1;
				}
// timeFires > nextTime là dấu hiệu rằng lửa sẽ không thể lan tới
// nếu thiết lập timeFires = -1 thì điều này sẽ không còn đúng nữa
				if (timeFires[nX][nY] > nextTime) {
					visited[nX][nY] = true;
					backtrack(nX, nY, nextTime, point + diamondMap[nX][nY]);
					visited[nX][nY] = false;
				}
			}
		}
		// visited[x][y] = false;
	}

	public static void print(int[][] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
	}
}

class Queue {
	int[] queue;
	int front, rear;
	int size, capacity;

	public Queue(int maxSize) {
		queue = new int[maxSize];
		front = 0;
		rear = -1;
		size = 0;
		capacity = maxSize;
	}

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void add(int item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear++;
		queue[rear] = item;
		size++;
	}

	int poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		int item = queue[front];
		queue[front] = 0;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front++;
		}
		size--;
		return item;
	}

	int front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	int rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	boolean isEmpty() {
		return size == 0;
	}

	boolean isFull() {
		return size == capacity;
	}

	void print() {
		for (int i = front; i <= rear; i++) {
			System.out.print(queue[i] + " ");
		}
		System.out.println();
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Hugo_GoldMining2 {
	static int N, G, Answer;
	static int[][] map;
	static int[] goldX, goldY;
	static int[][] visit;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\Hugo_DaoVang2_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			G = sc.nextInt();
			map = new int[N][N];
			goldX = new int[N];
			goldY = new int[N];
			for (int i = 0; i < G; i++) {
				goldX[i] = sc.nextInt() - 1;
				goldY[i] = sc.nextInt() - 1;
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			// danh dau nhung vi tri co vang
			for (int i = 0; i < G; i++) {
				map[goldX[i]][goldY[i]] = 2;
			}
			Answer = -1;
			// BFS tung o trong map - cac o so 1
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 1) {
						visit = new int[N][N];
						BFS(i, j);
					}
				}
			}

			System.out.println("Case #" + tc);
			if (Answer == -1) {
				System.out.println(-1);
			} else {
				System.out.println(Answer - 1);
			}
		}
	}

	public static void BFS(int i, int j) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(i);
		queue.add(j);
		visit[i][j] = 1;
		while (!queue.isEmpty()) {
			int curX = queue.poll();
			int curY = queue.poll();
			for (int k = 0; k < 4; k++) {
				int nextX = curX + dx[k];
				int nextY = curY + dy[k];
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
					if (visit[nextX][nextY] == 0 && map[nextX][nextY] != 0) {
						visit[nextX][nextY] = visit[curX][curY] + 1;
						queue.add(nextX);
						queue.add(nextY);
					}
				}
			}
		}
		int count = 0;
		int Max = Integer.MIN_VALUE;
		for (int k = 0; k < G; k++) {
// xet G vi tri mo vang, xem vi tri co visit lon nhat, và đếm xem có bao nhiêu vị trí có thể tới
			if (visit[goldX[k]][goldY[k]] > 0) {
				count++;
				Max = Math.max(Max, visit[goldX[k]][goldY[k]]);
			}
		}
		if (count == G) {
			if (Answer == -1 || Answer > Max) {
				Answer = Max;
			}
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class HugoBanDau_BFS {
	static int N, M, xhugo, yhugo, mana;
	static int[][] map = new int[50][50];
	static int[][] visit;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int count;
	// mạng kết nối
	// số đầu là số khả năng kết nối
	// các số sau từ 0 -> 3 chính là index cho cặp dx, dy
	static int[][] matrix = { { 0, 0, 0, 0, 0 }, { 4, 0, 1, 2, 3 }, { 2, 0, 1, 0, 0 }, { 2, 2, 3, 0, 0 },
			{ 2, 1, 3, 0, 0 }, { 2, 0, 3, 0, 0 }, { 2, 2, 0, 0, 0 }, { 2, 2, 1, 0, 0 } };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\HugoDau_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			xhugo = sc.nextInt();
			yhugo = sc.nextInt();
			mana = sc.nextInt();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			visit = new int[N][M];
			BFS();
			System.out.println("Case #" + (tc + 1));
			System.out.println(count);
		}
	}

	static void BFS() {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(xhugo);
		queue.add(yhugo);
		count = 0;
		visit[xhugo][yhugo] = 1;
		int curVal, k, nextVal, h;
		while (!queue.isEmpty()) {
			int x = queue.poll();
			int y = queue.poll();
			count++;
			curVal = map[x][y]; // gia tri o current
			if (visit[x][y] + 1 > mana) {
				continue;
			}
			for (int i = 0; i < matrix[curVal][0]; i++) {
				// index huong ma curVal co the ket noi toi
				// BFS nhưng chỉ xét ô bên cạnh mà nó có thể kết nối tới
				k = matrix[curVal][i + 1];
				int nextX = x + dx[k];
				int nextY = y + dy[k];
				if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
					nextVal = map[nextX][nextY];
					for (int j = 0; j < matrix[nextVal][0]; j++) {
						h = matrix[nextVal][j + 1]; // cặp (0,1) và (2,3)
						if ((h + k == 1 || h + k == 5) && visit[nextX][nextY] == 0) {
							visit[nextX][nextY] = visit[x][y] + 1;
							queue.add(nextX);
							queue.add(nextY);
//							visit[nextX][nextY] = visit[x][y] + 1;
//							if (visit[nextX][nextY] <= mana) {
//								queue.add(nextX);
//								queue.add(nextY);
//							}
						}
					}
				}
			}
		}
	} // ham BFS
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class IceCave {
	static int N, M;
	static int startX, startY, endX, endY;
	static int[][] map;
	static boolean[][] visit;
	static Queue queue = new Queue(2500000);
	static int[] dx = { -1, 0, 0, 1 };
	static int[] dy = { 0, 1, -1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\IceCave_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			startX = sc.nextInt();
			startY = sc.nextInt();
			endX = sc.nextInt();
			endY = sc.nextInt();
			map = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			System.out.println("Case " + tc);
//			System.out.println(startX + " " + startY);
//			System.out.println(N + " " + M);
			queue.init();
			visit = new boolean[N + 1][M + 1];
			if (bfs(startX, startY)) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}

	static boolean bfs(int startX, int startY) {
		if (startX == endX && startY == endY) {
			return true;
		}
		queue.add(startX, startY);
		visit[startX][startY] = true;
		int r, c, nR, nC;
		while (!queue.isEmpty()) {
			Point point = queue.get();
			r = point.x;
			c = point.y;
			for (int i = 0; i < 4; i++) {
				nR = r + dx[i];
				nC = c + dy[i];
				if (nR >= 0 && nR < N && nC >= 0 && nC < M && !visit[nR][nC]) {
					if (nR == endX && nC == endY) {
						if (map[nR][nC] == 0) {
							return true;
						} else {
							int count = 0;
							for (int j = 0; j < 4; j++) {
								int nX = nR + dx[j];
								int nY = nC + dy[j];
								if (nX >= 0 && nX < N && nY >= 0 && nY < M && map[nX][nY] == 1) {
									count++;
								}
							}
							if (count >= 2) {
								return true;
							}
							return false;
						}

					}
					if (map[nR][nC] == 1) {
						queue.add(nR, nC);
						visit[nR][nC] = true;
					}

				}
			}
		}

		return false;
	}

}

class Point {
	int x, y;

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class LangMac_BFS {
	static int N;
	static int[][] map;
	static boolean[] visited;
	static int regions;
	static int isolatedVillages;
//	static int countIsolate;
	static int bridges;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\LangMac_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			map = new int[N][N];
			visited = new boolean[N];
			regions = 0;
			isolatedVillages = 0;
			bridges = 0;

			// countIsolate = 0;
			for (int i = 0; i < N; i++) {
				// boolean flag = false;
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
//					if (map[i][j] == 1) {
//						flag = true;
//					}
				}
//				if (!flag) {
//					countIsolate++;
//				}
			}
			// ko reset mảng visited
			for (int i = 0; i < N; i++) {
				if (!visited[i]) {
					regions++;
					bfs(i);
				}
			}

			for (int i = 0; i <= N - 2; i++) {
				for (int j = i + 1; j <= N - 1; j++) {
					if (map[i][j] == 1) {
						map[i][j] = map[j][i] = 0;
						if (isBridge(i, j)) {
							bridges++;
						}
						map[i][j] = map[j][i] = 1;
					}
				}
			}

			System.out.println(regions + " " + isolatedVillages + " " + bridges);
			// System.out.println(countIsolate);
		}
	}

	public static void bfs(int s) {
		Queue<Integer> q = new LinkedList<>();
		q.add(s);
		visited[s] = true;
		boolean isIsolated = true;
		while (!q.isEmpty()) {
			int u = q.poll();
			for (int v = 0; v < N; v++) {
				if (map[u][v] == 1 && !visited[v]) {
					visited[v] = true;
					q.add(v);
					isIsolated = false;
				}
			}
		}

		if (isIsolated) {
			isolatedVillages++;
		}
	}

	public static boolean isBridge(int u, int v) {
		Queue<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[N];
		q.add(u);
		visited[u] = true;

		while (!q.isEmpty()) {
			int x = q.poll();
			for (int y = 0; y < N; y++) {
				if (map[x][y] == 1 && !visited[y]) {
					if (y == v) {
						return false;
					}
					visited[y] = true;
					q.add(y);
				}
			}
		}

		return true;
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class LaughingBomb {
	static int N, M;
	static int[][] matrix, time;

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

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\LaughingBomb_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			matrix = new int[M][N];
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			// int[][] distance = new int[101][101];
			int ybomb = sc.nextInt() - 1;
			int xbomb = sc.nextInt() - 1;
			time = new int[M][N];

			// Queue queue = new Queue(300000);
			Queue<Integer> queue = new LinkedList<>();
			queue.add(xbomb);
			queue.add(ybomb);
			time[xbomb][ybomb] = 1;
			while (!queue.isEmpty()) {
				int curX = queue.poll();
				int curY = queue.poll();
				// int curStep = time[curX][curY];
				for (int i = 0; i < 4; i++) {
					int nextX = curX + dx[i];
					int nextY = curY + dy[i];
					if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N && matrix[nextX][nextY] == 1) {
						if (time[nextX][nextY] == 0) {
							time[nextX][nextY] = time[curX][curY] + 1;
							queue.add(nextX);
							queue.add(nextY);
						}

					}
				}
			}
			// printArr(time);
			int maxTime = 0;
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					if (matrix[i][j] == 1) {
						maxTime = Math.max(maxTime, time[i][j]);
					}
				}
			}

			System.out.println(maxTime);
		}
	}

	public static void printArr() {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MapColoring {
	static int N, E;
	static boolean[][] map;
	static int[] color;
	static boolean[] visited;
	static boolean flag;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\MapColoring_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			E = sc.nextInt();
			map = new boolean[N][N];
			color = new int[N];
			for (int i = 0; i < N; i++) {
				color[i] = -1;
			}
			color[0] = 0;
			for (int i = 0; i < E; i++) {
				int u = sc.nextInt() - 1;
				int v = sc.nextInt() - 1;
				map[u][v] = map[v][u] = true;
			}
			visited = new boolean[N];
			flag = true;
//			for (int i = 0; i < N; i++) {
//				if (!visited[i]) {
//					bfs(i);
//				}
//				if (!flag) {
//					break;
//				}
//			}
			// đồ thị liên thông nên chỉ cần một lượt
			bfs(0);

			if (!flag) {
				System.out.println("#" + tc + " " + -1);
			} else {
				System.out.print("#" + tc + " ");
				for (int i = 0; i < N; i++) {
					System.out.print(color[i]);
				}
				System.out.println();
			}
		}
	}

	public static void bfs(int start) {
		// Queue<Integer> queue = new LinkedList<>();
		Queue queue = new Queue(3000);
		queue.add(start);
		visited[start] = true;
		color[start] = 0;
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			for (int next = 0; next < N; next++) {
				if (map[cur][next]) { // co canh
					if (!visited[next]) { // dinh nay chua duoc tham
						visited[next] = true;
						color[next] = Math.abs(color[cur] - 1); // 1 - color[cur];
						queue.add(next);
					} else if (color[cur] != color[next]) { // visited[next] = true
						continue;
					} else {
						flag = false;
						break;
					}
				}
			}
			if (!flag) {
				break;
			}
		}
	}

	public static boolean checkMap() {
		for (int u = 0; u < N - 1; u++) {
			for (int v = u + 1; v < N; v++) {
				if (map[u][v] && color[u] == color[v]) {
					return false;
				}
			}
		}
		return true;
	}
}

package BFS;

// lưu ý kỹ thuật thử chiều cao để BFS
// cách viết BFS kiểu boolean - tìm đường
// cách dựng dx, dy
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class MarioClimbing {
	static int N, M, Answer;
	static int startX, startY, endX, endY;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx, dy;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\MarioClimbing_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			map = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 2) {
						startX = i;
						startY = j;
					}
				}
			}

			// lập mảng di chuyển dựa theo giá trị bước nhảy h
			dx = new int[102];
			int step = 0;
			for (int i = 0; i <= 2 * N - 1; i += 2) { // dx chứa 2*N giá trị
				dx[i] = step;
				dx[i + 1] = -step;
				step++;
			}
			dy = new int[102];
			dy[0] = -1;
			dy[1] = 1;
			// Thử từng chiều cao
			for (int h = 0; h < N; h++) {
				if (BFS(h)) {
					Answer = h;
					break;
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(Answer);
		}
	}

	static boolean BFS(int jump) {
		// Queue queue = new Queue(10000);
		Queue<Integer> queue = new LinkedList<Integer>();
		visit = new boolean[N][M];
		queue.add(startX);
		queue.add(startY);
		visit[startX][startY] = true;
		while (!queue.isEmpty()) {
			int cx = queue.poll();
			int cy = queue.poll();
			if (map[cx][cy] == 3) {
				return true;
			}
			for (int i = 0; i < 2 * (jump + 1); i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visit[nx][ny] && map[nx][ny] != 0) {
					visit[nx][ny] = true;
					queue.add(nx);
					queue.add(ny);
				}
			}
		}
		return false;
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class MountainWalking_BinaryBFS {
	static int N, Answer;
	static int MAX, MIN;
	static int[][] map;
	static boolean[][] visited;

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

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\MountainWalking_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			MIN = Integer.MAX_VALUE;
			MAX = Integer.MIN_VALUE;
			Answer = 0;
			N = sc.nextInt();
			map = new int[N][N];
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
					MAX = Math.max(MAX, map[i][j]);
					MIN = Math.min(MIN, map[i][j]);
				}
			int L = 0, R = MAX - MIN;
			while (L <= R) {
				int mid = (L + R) / 2;
				if (bfs(mid)) {
					Answer = mid;
					R = mid - 1;
				} else {
					L = mid + 1;
				}
			}

			System.out.println("#" + tc + " " + Answer);

			// while (L < R) {
			// int mid = (L + R) / 2;
			// if (bfs(mid)) {
			// //Answer = mid;
			// R = mid;
			// } else {
			// L = mid + 1;
			// }
			// }
			// System.out.println("#" + tc + " " + L);

		}
		sc.close();
	}

	public static boolean bfs(int checkPoint) {
// với cùng 1 giá trị checkpoint, có nhiều giá trị cận trên - right, cận dưới - left
		for (int left = MIN; left <= MAX - checkPoint; left++) {
			int right = left + checkPoint;
			if (map[0][0] < left || map[0][0] > right || map[N - 1][N - 1] < left || map[N - 1][N - 1] > right) {
				continue;
			}

			visited = new boolean[N][N];
			visited[0][0] = true;
			Queue<int[]> queue = new LinkedList<>();
			queue.add(new int[] { 0, 0 });
			while (!queue.isEmpty()) {
				int[] cur = queue.poll();
				int curX = cur[0];
				int curY = cur[1];
				if (curX == N - 1 && curY == N - 1) {
					return true;
				}
				for (int k = 0; k < 4; k++) {
					int u = curX + dx[k];
					int v = curY + dy[k];
					if (u >= 0 && u < N && v >= 0 && v < N) {
						if (map[u][v] >= left && map[u][v] <= right && !visited[u][v]) {
							visited[u][v] = true;
							queue.add(new int[] { u, v });
						}
					}
				}
			}
		}
// thử vết trường hợp trong vòng for mà không return được true thì return false ở cuối
		return false;
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MountainWalking_BinaryBFS2 {
	static int n;
	static int[][] mountain = new int[100][100];
	static int front, rear;
	static boolean[][] visited = new boolean[100][100];
	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { -1, 0, 1, 0 };
	static int[] queueX = new int[1000000];
	static int[] queueY = new int[1000000];

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\MountainWalking_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++) {
				for (int j = 0; j < n; j++) {
					mountain[i][j] = sc.nextInt();
				}
			}
			int left = 0, right = 110;
			while (left < right) {
				int mid = (left + right) / 2;
				boolean flag = false;
				for (int i = 0; i <= 110; i++) {
					visited = new boolean[n][n];
					visited[0][0] = true;
					BFS(0, 0, i, i + mid);
					if (visited[n - 1][n - 1]) {
						flag = true;
						break;
					}
				}
				if (flag)
					right = mid;
				else
					left = mid + 1;
			}

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

	public static void BFS(int x, int y, int start, int end) {
		if (mountain[x][y] < start || mountain[x][y] > end)
			return;
		front = rear = 0;
		queueX[rear] = x;
		queueY[rear] = y;
		rear++;
		while (front < rear) {
			int xx = queueX[front];
			int yy = queueY[front];
			front++;
			for (int i = 0; i < 4; i++) {
				int _x = xx + dx[i];
				int _y = yy + dy[i];
				if (_x >= 0 && _x < n && _y >= 0 && _y < n) {
					if (!visited[_x][_y]) {
						if (mountain[_x][_y] >= start && mountain[_x][_y] <= end) {
							visited[_x][_y] = true;
							queueX[rear] = _x;
							queueY[rear] = _y;
							rear++;
						}
					}
				}
			}
		}
	}

}

package BFS;

// ý tưởng của bài này là khiến một số ô không thể loang tới được - bị ngập nước
// bài này có tư tưởng tìm ô chưa đánh dấu để BFS, tức BFS nhiều lần trong 2 vòng for
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class NuocBien {
	static int N, M;
	static int[][] map;
	static int Min, Max;
	static boolean[][] visit, visit_water;
	static int Answer;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };
	static int NumberOfParts;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\NuocBien_input.txt"));
		Scanner sc = new Scanner(System.in);
		int tc = 1;
		while (true) {
			N = sc.nextInt();
			M = sc.nextInt();
			if (M == 0 && N == 0) {
				break;
			}
			map = new int[N][M];
			Min = Integer.MAX_VALUE;
			Max = Integer.MIN_VALUE;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();

				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					Max = Math.max(Max, map[i][j]);
					if (i == 0 || j == 0 || i == N - 1 || j == M - 1) {
// tim min theo gia tri o vien vi nuoc bien xam lan tu day
						Min = Math.min(Min, map[i][j]);
					}
				}
			}

			Answer = -1;
			// Queue<Integer> queue = new LinkedList<>();
			// tìm độ cao min cho mực nước dâng
			for (int k = Min; k < Max; k++) {
				visit = new boolean[N][M];
				visit_water = new boolean[N][M];

				// cap nhat mang visit_water
				BFS_Water(k);
				if (BFS(k)) {
					Answer = k;
					break;
				}
			}

			if (Answer == -1) {
				System.out.println("Case " + tc + ": " + "Island never splits.");
			} else {
				System.out.println("Case " + tc + ": " + "Island splits when ocean rises " + Answer + " feet.");
			}
			tc++;

		}
	}

	public static void BFS_Water(int feet) {
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visit_water[i][j] && map[i][j] <= feet && (i == 0 || j == 0 || i == N - 1 || j == M - 1)) {
					queue.add(i);
					queue.add(j);
					visit_water[i][j] = true;
					while (!queue.isEmpty()) {
						int curX = queue.poll();
						int curY = queue.poll();
						for (int k = 0; k < 4; k++) {
							int nextX = curX + dx[k];
							int nextY = curY + dy[k];
							if (nextX >= 0 && nextY >= 0 && nextY < M && nextX < N && !visit_water[nextX][nextY]
									&& map[nextX][nextY] <= feet) {
								visit_water[nextX][nextY] = true;
								queue.add(nextX);
								queue.add(nextY);
							}
						}
					}
				}

			}
		}
	}

// BFS tìm số thành phần
	public static boolean BFS(int feet) {
		NumberOfParts = 0;
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				// bfs được 1 cụm -> tăng numberOfParts
				if (!visit[i][j] && !visit_water[i][j]) {
					queue.add(i);
					queue.add(j);
					visit[i][j] = true;
					while (!queue.isEmpty()) {
						int curX = queue.poll();
						int curY = queue.poll();
						for (int k = 0; k < 4; k++) {
							int nextX = curX + dx[k];
							int nextY = curY + dy[k];
							if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M && !visit[nextX][nextY]
									&& !visit_water[nextX][nextY]) {
								visit[nextX][nextY] = true;
								queue.add(nextX);
								queue.add(nextY);
							}
						}
					}
					NumberOfParts++;
				}
			}
		}

		if (NumberOfParts == 1)
			return false;
		else
			return true;
		// th = 0 --> tất cả các ô ngập nước
		// th > 1 --> bị chia cắt
	}

}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class PhaHuyHeThongDien_BFS {
	static int N;
	static int[][] graph;
	static boolean[] visited;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\PhaHuyHeThongDien_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while (T-- > 0) {
			N = sc.nextInt();
			graph = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					graph[i][j] = sc.nextInt();
				}
			}
			// tinh so component ban đầu, vì đề bài yêu cầu so sánh số component
			// sau khi xóa có tăng lên hay không
			int initialComponents = 0;
			visited = new boolean[N];
			for (int i = 0; i < N; i++) {
				if (!visited[i]) {
					bfs(i);
					initialComponents++;
				}
			}

			int maxComponents = initialComponents;
			// int maxComponents = 0;
			int islandToDestroy = 0;
			// mỗi lần chọn một điểm i để xóa cần reset visited
			for (int i = 0; i < N; i++) {
				// khi xóa điểm i và các cạnh nối tới i, ta không cần phải thay
				// các giá trị 1 -> 0 trong matrix, chỉ cần đánh dấu i là true
				// để bfs không lan tới
				visited = new boolean[N];
				visited[i] = true;
				// for (int j = 0; j < N; j++) {
				// graph[i][j] = graph[j][i] = 0;
				// }
				int components = 0;
				for (int j = 0; j < N; j++) {
					// mỗi lần có thể bfs là mỗi lần số component tăng lên
					if (!visited[j]) {
						bfs(j);
						components++;
					}
				}
				if (components > maxComponents) {
					maxComponents = components;
					islandToDestroy = i + 1;
				}
			}
			System.out.println(islandToDestroy);
		}
	}

	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		// Queue queue = new Queue(1000);
		queue.add(start);
		visited[start] = true;
		while (!queue.isEmpty()) {
			int node = queue.poll();
			for (int i = 0; i < N; i++) {
				if (graph[node][i] == 1 && !visited[i]) {
					queue.add(i);
					visited[i] = true;
				}
			}
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Princess {
	static int N;
	static int[][] maze, visit;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\Princess_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			maze = new int[N][N];
			int pX = 0, pY = 0; // tọa độ của công chúa
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					maze[i][j] = sc.nextInt();
					if (maze[i][j] == 2) {
						pX = i;
						pY = j;
					}
				}
			}
			int res = -1;
			int kq1 = BFS(0, 0, pX, pY);
			int kq2 = BFS(pX, pY, N - 1, N - 1);
			if (kq1 == -1 || kq2 == -1) {
				res = -1;
			} else {
				res = kq1 + kq2;
			}
			System.out.println(res);
		}
	}

	public static int BFS(int startX, int startY, int endX, int endY) {
		Queue<Integer> queue = new LinkedList<Integer>();
		visit = new int[N][N];
		queue.add(startX);
		queue.add(startY);
		visit[startX][startY] = 1;
		while (!queue.isEmpty()) {
			int curX = queue.poll();
			int curY = queue.poll();
			for (int i = 0; i < 4; i++) {
				int nextX = curX + dx[i];
				int nextY = curY + dy[i];
				if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N && maze[nextX][nextY] != 0
						&& visit[nextX][nextY] == 0) {
					queue.add(nextX);
					queue.add(nextY);
					visit[nextX][nextY] = visit[curX][curY] + 1;
					if (nextX == endX && nextY == endY) {
						return visit[nextX][nextY] - 1;
					}
				}
			}
		}
		return -1;
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SkyMap {
	static int n;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\SkyMap_input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t-- > 0) {
			n = sc.nextInt();
			map = new int[n][n];
			visited = new boolean[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			int count = 0; // đếm số vùng
			int Longest = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (map[i][j] == 1 && !visited[i][j]) {
						count++;
						Longest = Math.max(Longest, bfs(i, j));
					}
				}
			}
			System.out.println(count + " " + Longest);
		}
	}

	// x, y la toa do o xuat phat
	public static int bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { x, y });
		visited[x][y] = true;
		int stars = 1;
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			for (int i = 0; i < 4; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				if (nx >= 0 && nx < n && ny >= 0 && ny < n && map[nx][ny] == 1 && !visited[nx][ny]) {
					queue.offer(new int[] { nx, ny });
					visited[nx][ny] = true;
					stars++;
				}
			}
		}
		return stars;
	}

}

package BFS;

// cách làm này không cần sử dụng tempMap vì khéo léo sử dụng mảng visit
// BFS loang lân cận bằng đệ quy spread
// initBFS chứa find(), find() lại chứa spread --> cập nhật mảng count và thực hiện replace
// replace tìm Max, thực hiện hoàn nguyên đánh dấu, gần = reset visit. Lý do không reset visit trong 
// initBFS vì còn cần khéo léo đặt visit những ô 0 = -1 để sau này không bị xét lân cận khi đã có giá trị 
// khác 0
// lưu  ý cách dùng vòng while để đổi giá trị, rất khác so với cách làm thứ 2
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class ThongTriAPS2_Cach1 {
	static int N, Max;
	static int[][] map, visit;
	static int[] count;
	static Queue<Integer> queue;
	static Queue<Integer> qSave;
	// static Queue queue;
	// static Queue qSave;
	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { -1, 0, 1, 0 };
	static int Answer;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\ThongTriKhuVuc_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			map = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			Answer = 0;
			count = new int[6];
			visit = new int[N][N];
			initBFS();
			countRegion();
			System.out.println("Case #" + tc);
			System.out.println(Answer);
		}
	}

	static void initBFS() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0 && visit[i][j] == 0) {
					count = new int[6];
					visit[i][j] = 1;
					queue = new LinkedList<>();
					qSave = new LinkedList<>();
					// queue = new Queue(20000);
					// qSave = new Queue(20000);
					queue.add(i);
					queue.add(j);
					qSave.add(i);
					qSave.add(j);
					find();
				}
			}
		}
	}

	static void find() {
		while (!queue.isEmpty()) {
			int x = queue.poll();
			int y = queue.poll();
			for (int i = 0; i < 4; i++) {
				int _x = x + dx[i];
				int _y = y + dy[i];
				if (_x >= 0 && _x < N && _y >= 0 && _y < N) {
					if (map[_x][_y] == 0 && visit[_x][_y] == 0) {
						visit[_x][_y] = 1;
						queue.add(_x);
						queue.add(_y);
						qSave.add(_x);
						qSave.add(_y);
					} else if (map[_x][_y] != 0 && visit[_x][_y] == 0) {
						count[map[_x][_y]]++;
						visit[_x][_y] = 1;
						spread(_x, _y);
					}
				}
			}
		}
		replace();
	}

	static void spread(int x, int y) {
		for (int j = 0; j < 4; j++) {
			int _xx = x + dx[j];
			int _yy = y + dy[j];
			if (_xx >= 0 && _xx < N && _yy >= 0 && _yy < N) {
				if (map[_xx][_yy] == map[x][y] && visit[_xx][_yy] == 0) {
					count[map[x][y]]++;
					visit[_xx][_yy] = 1;
					spread(_xx, _yy);
				}
			}
		}
	}

	public static void replace() {
		Max = 0;
		int val = 0;
		for (int i = 5; i >= 1; i--) {
			if (count[i] > Max) {
				Max = count[i];
				val = i;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visit[i][j] == 1) {
					visit[i][j] = 0;
				}
			}
		}
		// không thể dùng visit ở đây vì nó sẽ thay đổi cả các ô có giá trị -1
		// visit = new int[N][N];
		while (!qSave.isEmpty()) {
			int x = qSave.poll();
			int y = qSave.poll();
			map[x][y] = val;
			visit[x][y] = -1; // tránh việc bị đếm lân cận vào sau này
		}
	}

	static void countRegion() {
		visit = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visit[i][j] == 0) {
					visit[i][j] = 1;
					queue = new LinkedList<>();
					// queue = new Queue(20000);
					queue.add(i);
					queue.add(j);
					while (!queue.isEmpty()) {
						int x = queue.poll();
						int y = queue.poll();
						for (int k = 0; k < 4; k++) {
							int _x = x + dx[k];
							int _y = y + dy[k];
							if (_x >= 0 && _x < N && _y >= 0 && _y < N) {
								if (map[_x][_y] == map[x][y] && visit[_x][_y] == 0) {
									visit[_x][_y] = 1;
									queue.add(_x);
									queue.add(_y);
								}
							}
						}
					}
					Answer++;
				}
			}
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

// queue1 lưu những ô 0
// queue2 lưu những ô kề cận khác 0
// count[] đếm số lần xuất hiện của từng giá trị xung quanh 0
// do mỗi lần lại được lấy ra để check xung quanh nên sẽ tới thời điểm queue1 rỗng
// nhưng ta lại cần biết lịch sử những ô 0 được thêm vào queue để chuyển đổi giá trị của nó
// có 2 cách, cách thứ nhất là dùng một queue khác chỉ để nhét phần tử vào
// cách 2 là dùng rear để track lịch sử
// phải sử dụng newMap vì map gốc được dùng để đếm ô lân cận, đếm ô lân cận theo map gốc
// chính là hàm CheckAround
// còn thay đổi giá trị ô 0, tìm ô 0 để BFS, đếm vùng là thực hiện trên newMap

// mỗi lần tìm được 1 số 0 để BFS ra một vùng thì queue1, visit và count đều phải reset
// trong đó, queue1 để chứa những số 0 trong một vùng để thay đổi
// visit dùng để BFS
// count để đếm tần số xuất hiện của giá trị lân cận
// BFS CheckAround chính là một phần của BFS FindZeros
// mỗi lần BFS CheckAround queue2 dùng để lưu trữ giá trị lân cận sẽ được reset, chủ yếu là tránh
// tràn mảng khi phần tử rear đi quá giới hạn
// cũng để an toàn đi, vì mỗi lần queue2 reset, coi như queue2 sau đó chỉ chứa duy nhất 1 giá trị ô và đếm
// visit tiếp tục được dùng để BFS ở CheckAround
// quan trọng hơn cả là mảng count được cập nhật liên tục mối khi queue2 add
// CheckAround dùng dữ liệu của map gốc

// 3 yếu tố được reset để thực hiện BFS đếm vùng
// lưu ý nếu có nhiều phần tử có cùng freq thì lấy phần tử có giá trị Max --> lưu ý cách viết hàm
// findMax
// lưu ý cách viết queue, sử dụng queue, hàm findMax...của bài toán này
// lưu ý cách loang BFS...OOP
public class ThongTriKhuVuc_Optimal {
	static int N, Answer;
	static int[][] map, newMap, visit;
	static int[] count;
	static Queue queue1 = new Queue(10005);
//	static Queue bonusQ = new Queue(10005);
	static Queue queue2 = new Queue(10005);
	static int[] dX = { 0, -1, 0, 1 };
	static int[] dY = { -1, 0, 1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\ThongTriKhuVuc_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			Answer = 0;
			map = new int[N][N];
			newMap = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
					newMap[i][j] = map[i][j];
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (newMap[i][j] == 0) { // tìm các ô 0 để BFS
						FindZeros(i, j);
						int val = findMax();
						// thay đổi giá trị của các cụm ô 0 liền kề với i,j
						for (int k = 0; k <= queue1.rear; k++) {
							Square toado = queue1.get(k);
							newMap[toado.r][toado.c] = val;
						}
//						for (int k = 0; k < bonusQ.size; k++) {
//							Square toado = bonusQ.get(k);
//							newMap[toado.r][toado.c] = val;
//						}
					}
				}
			}

			queue1.reset();
			visit = new int[N][N];
			count = new int[6];

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (visit[i][j] == 0) {
						CountAreas(i, j);
						Answer++;
					}
				}
			}

			System.out.println("Case #" + tc + "\n" + Answer);
		}
	}

// BFS Find 0s and kick off BFS find max frequency around
	public static void FindZeros(int r, int c) {
		queue1.reset();
		// bonusQ.reset();
		visit = new int[N][N];
		count = new int[6];
		visit[r][c] = 1;
		queue1.add(new Square(r, c));
		// bonusQ.add(new Square(r, c));

		while (!queue1.isEmpty()) {
			Square toado = queue1.poll();
			for (int i = 0; i < 4; i++) {
				int nR = toado.r + dX[i];
				int nC = toado.c + dY[i];
				if (nR >= 0 && nR < N && nC >= 0 && nC < N && visit[nR][nC] == 0) {
					if (newMap[nR][nC] == 0) {
						visit[nR][nC] = 1;
						queue1.add(new Square(nR, nC));
						// bonusQ.add(new Square(nR, nC));
					} else {
						CheckAround(nR, nC);
					}
				}
			}
		}
	}

// BFS Check Around to find max frequency
	public static void CheckAround(int r, int c) {
		queue2.reset(); // nếu không reset có thể dẫn đến tràn mảng
		visit[r][c] = 1;
		queue2.add(new Square(r, c));
		count[map[r][c]]++;
		while (!queue2.isEmpty()) {
			Square toado = queue2.poll();
			int curX = toado.r;
			int curY = toado.c;
			for (int i = 0; i < 4; i++) {
				int nextX = curX + dX[i];
				int nextY = curY + dY[i];
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && visit[nextX][nextY] == 0) {
					if (map[nextX][nextY] == map[curX][curY]) {
						visit[nextX][nextY] = 1;
						queue2.add(new Square(nextX, nextY));
						count[map[nextX][nextY]]++;
					}
				}
			}
		}
	}

	// BFS Count Areas
	public static void CountAreas(int r, int c) {
		visit[r][c] = 1;
		queue1.add(new Square(r, c));
		while (!queue1.isEmpty()) {
			Square toado = queue1.poll();
			for (int i = 0; i < 4; i++) {
				int nR = toado.r + dX[i];
				int nC = toado.c + dY[i];
				if (nR >= 0 && nR < N && nC >= 0 && nC < N && visit[nR][nC] == 0) {
					if (newMap[nR][nC] == newMap[toado.r][toado.c]) {
						visit[nR][nC] = 1;
						queue1.add(new Square(nR, nC));
					}
				}
			}
		}
	}

	public static int findMax() {
		int maxFreq = -1;
		int val = 0;
		for (int i = 1; i < 6; i++) {
			if (count[i] >= maxFreq) {
				maxFreq = count[i];
				val = i;
			}
		}
		return val;
	}

	static class Square {
		int r, c;

		Square(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static class Queue {
		Square[] queue;
		int front, rear;
		int size, capacity;

		public Queue(int maxSize) {
			queue = new Square[maxSize];
			front = 0;
			rear = -1;
			size = 0;
			capacity = maxSize;
		}

		void reset() {
			front = 0;
			rear = -1;
			size = 0;
		}

		void add(Square item) {
			rear++;
			queue[rear] = item;
			size++;
		}

		Square poll() {
			Square item = queue[front];
			front++;
			size--;
			return item;
		}

		Square get(int index) {
			return queue[index];
			// return queue[front + index]
			// return queue[(front + index) % capacity];
		}

		boolean isEmpty() {
			return size == 0;
		}
	}

}

package BFS;

// tư tưởng của cách này là bfs vùng nào thì đánh dấu giá trị của vùng đó
// nếu sao đó vẫn có ô có giá trị này mà chưa được visited thì chứng tỏ có phân mảnh
// một cách sáng tạo hơn nữa là đếm số thành phần components, nếu số thành phần bằng đúng N thì đáp án
// là good, nếu số thành phần lớn hơn N thì wrong
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class UniformSquare_Cach1 {
	static int N;
	static int[][] matrix;
	static boolean[][] visited;
	static boolean[] CheckIn;
	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { -1, 0, 1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\UniformSquare_input.txt"));
		// System.setIn(new
		// FileInputStream("src\\BFS\\UniformSquare_input2.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			matrix = new int[N][N];
			for (int i = 1; i < N; i++) { // N-1 dong
				for (int j = 0; j < N; j++) {
					matrix[sc.nextInt() - 1][sc.nextInt() - 1] = i;
				}
			}
			visited = new boolean[N][N];
			CheckIn = new boolean[N + 1];
			boolean flag = true;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (!visited[i][j]) {
						if (CheckIn[matrix[i][j]]) {
							flag = false;
							break;
						} else {
							CheckIn[matrix[i][j]] = true;
							Queue<Integer> queue = new LinkedList<>();
							queue.add(i);
							queue.add(j);
							visited[i][j] = true;
							while (!queue.isEmpty()) {
								int curX = queue.poll();
								int curY = queue.poll();
								for (int k = 0; k < 4; k++) {
									int nextX = curX + dx[k];
									int nextY = curY + dy[k];
									if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N && !visited[nextX][nextY]
											&& matrix[curX][curY] == matrix[nextX][nextY]) {
										visited[nextX][nextY] = true;
										queue.add(nextX);
										queue.add(nextY);
									}
								}
							}
						}
					}
				}
				if (!flag) {
					break;
				}
			}
			System.out.println("Case #" + tc);
			if (flag) {
				System.out.println("good");
			} else {
				System.out.println("wrong");
			}

		} // for tc
	}

	public static void print(int[][] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class UniformSquare_Cach2 {
	static int N;
	static int[][] map;
	static boolean[][] visit = new boolean[5][5];
	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { -1, 0, 1, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\UniformSquare_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			map = new int[5][5];
			for (int i = 1; i <= N - 1; i++) {
				for (int j = 0; j <= N - 1; j++) {
					map[sc.nextInt() - 1][sc.nextInt() - 1] = i;
				}
			}
			clear();
			boolean flag = true;
			for (int k = 0; k <= N - 1; k++) {
				for (int i = 0; i <= N - 1; i++) {
					for (int j = 0; j <= N - 1; j++) {
						if (!visit[i][j] && map[i][j] == k) {
							bfs(i, j, k);
						}
					}
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (!visit[i][j]) {
						flag = false;
					}
				}
			}

			System.out.println("Case #" + tc);
			if (flag) {
				System.out.println("good");
			} else {
				System.out.println("wrong");
			}
		}
	}

// k là giá trị của map[xS][yS]
	static void bfs(int xS, int yS, int k) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(xS);
		queue.add(yS);
		do {
			int x = queue.poll();
			int y = queue.poll();
			for (int i = 0; i < 4; i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];
				if (newX >= 0 && newX < N && newY >= 0 && newY < N && !visit[newX][newY] && map[newX][newY] == k) {
					visit[newX][newY] = true;
					queue.add(newX);
					queue.add(newY);
				}
			}
		} while (!queue.isEmpty());
	}

	static void clear() {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				visit[i][j] = false;
			}
		}
	}
}

package BFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class ValidateMaze {
	static int N, M;
	static int[][] Maze;
	static boolean[][] visited;
	static int startX, startY, endX, endY;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\BFS\\ValidateMaze_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			M = sc.nextInt();
			N = sc.nextInt();
			Maze = new int[M][N];

			startX = startY = endX = endY = 0;
			int count = 0;
			for (int i = 0; i < M; i++) {
				String line = sc.next();
				for (int j = 0; j < N; j++) {
					if (line.charAt(j) == '#') {
						Maze[i][j] = 1;
					}
					if ((i == 0 || i == M - 1 || j == N - 1 || j == 0) && Maze[i][j] == 0) {
						count++;
						if (count == 1) {
							startX = i;
							startY = j;
						}
						if (count == 2) {
							endX = i;
							endY = j;
						}
					}
				}
			}
			if (count != 2) {
				System.out.println("invalid");
				continue;
			}
			visited = new boolean[M][N];
			boolean flag = false;
			// BFS
			Queue<Integer> queue = new LinkedList<>();
			queue.add(startX);
			queue.add(startY);
			visited[startX][startY] = true;
			while (!queue.isEmpty()) {
				int curX = queue.poll();
				int curY = queue.poll();
				for (int i = 0; i < 4; i++) {
					int nextX = curX + dx[i];
					int nextY = curY + dy[i];
					if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N && !visited[nextX][nextY]
							&& Maze[nextX][nextY] == 0) {
						if (nextX == endX && nextY == endY) {
							flag = true;
							break;
						}
						visited[nextX][nextY] = true;
						queue.add(nextX);
						queue.add(nextY);
					}
				}
				if (flag) {
					break;
				}
			}

			if (flag) {
				System.out.println("valid");
			} else {
				System.out.println("invalid");
			}
		} // for tc
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Catan_1 {
	static int N, M;
	static int[][] graph;
	static boolean[][] visited;
	static int maxDistance = 0;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\Catan_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			graph = new int[N][N];
			visited = new boolean[N][N];
			for (int i = 0; i < M; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				graph[u][v] = 1;
				graph[v][u] = 1;
			}
			maxDistance = 0;
			for (int i = 0; i < N; i++) {
				dfs(i, 0);
			}
			System.out.println(maxDistance);
		}

	}

	public static void dfs(int node, int distance) {
		maxDistance = Math.max(maxDistance, distance);
		for (int neighbor = 0; neighbor < N; neighbor++) {
			if (graph[node][neighbor] == 1 && !visited[node][neighbor]) {
				visited[node][neighbor] = true;
				visited[neighbor][node] = true;
				dfs(neighbor, distance + 1);
				visited[node][neighbor] = false;
				visited[neighbor][node] = false;
			}
		}
		// đặt maxDistance ở đây tối ưu hơn
//		maxDistance = Math.max(maxDistance, distance);
//		return;
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Catan_2 {
	static int N, M;
	static int[][] graph;
	static int[][] list;
	static int Answer;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\Catan_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			graph = new int[N][N];
			list = new int[N][N + 1];
			for (int i = 0; i < M; i++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				graph[u][v] = graph[v][u] = 1;
				list[u][0]++;
				list[u][list[u][0]] = v;
				list[v][0]++;
				list[v][list[v][0]] = u;

			}
			Answer = 0;
			for (int i = 0; i < N; i++) { // nhớ dfs tại N đỉnh
				dfs(i, 0);
			}
			System.out.println(Answer);
		}
	}

	// cách giải này không dùng mảng đánh dấu nhưng nó xóa cạnh
	public static void dfs(int x, int sum) {
		Answer = Math.max(sum, Answer);
		for (int i = 0; i < list[x][0]; i++) {
			if (graph[x][list[x][i + 1]] == 1) {
				graph[x][list[x][i + 1]] = graph[list[x][i + 1]][x] = 0;
				dfs(list[x][i + 1], sum + 1);
				graph[x][list[x][i + 1]] = graph[list[x][i + 1]][x] = 1;
			}
		}
//		if (sum > Answer) {
//			Answer = sum;
//		}
//		return;
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Diamond_DFS2 {
	static int N;
	static boolean[][] graph;
	static int[] numEdges;
	static boolean visited[];
	static boolean found;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\Diamond_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			graph = new boolean[N + 1][N + 1];
			numEdges = new int[N + 1];
			found = false;
			for (int i = 1; i <= N; i++) {
				numEdges[i] = sc.nextInt();
				for (int j = 0; j < numEdges[i]; j++) {
					int next = sc.nextInt();
					graph[i][next] = true;
				}
			}

			// dfs N dinh
			for (int i = 1; i <= N; i++) {
// chi nhung node co tren 2 canh di ra moi duoc chon, bắt đầu dfs, khởi tạo mới visited
				if (numEdges[i] >= 2) {
					visited = new boolean[N + 1];
					visited[i] = true;
					DFS(i);
				}
				if (found) { // toi uu
					break;
				}
			}

			if (found) {
				System.out.println("Case #" + tc + " \n" + "Yes");
			} else {
				System.out.println("Case #" + tc + " \n" + "No");
			}
		} // for tc

	}

	static void DFS(int from) {
		for (int i = 1; i <= N; i++) {
			if (graph[from][i]) {
				if (!visited[i]) {
					visited[i] = true;
					DFS(i);
				} else {
// neu visited[i] = true, dieu do co nghia la i da duoc tham truoc do boi mot DFS tu nhanh khac
					found = true;
					break;
				}
			}
		}
	}
}

package DFS;

// cách của anh Huys
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

// ky thuat loang theo chieu sau bang vong for
public class Diamond_DFS1 {
	static int[] visited;
	static int count, N;
	static int[] numEdges; // so canh cua moi dinh
	static int[][] next;
	static boolean found;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\Diamond_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			found = false;
			next = new int[1001][11];
			numEdges = new int[1001];
			for (int i = 1; i <= N; i++) {
				numEdges[i] = sc.nextInt();
				for (int j = 0; j < numEdges[i]; j++) {
					next[i][j] = sc.nextInt();
				}
			}
			for (int i = 1; i <= N; i++) {
				visited = new int[1001];
				count = 0;
// đánh số tất cả các nhánh từ i. trong đó i được đánh số theo nhánh cao nhất, 
// sau đó gọi DFS
				for (int j = 0; j < numEdges[i]; j++) { // phân nhánh
					if (visited[next[i][j]] > 0) {
						found = true;
					} else {
						visited[i] = visited[next[i][j]] = ++count;
						DFS(i, next[i][j]);
					}
				}

				// có thể check thêm điều kiện found ở đây
			}

			System.out.println("Case #" + tc);
			if (found) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}

		}
	}

	public static void DFS(int from, int v) {
		if (found) {
			return;
		}
// bài toán này là cạnh một chiều nên không thể bỏ đoạn code này, xét trường hợp tìm found ở bên ngoài là chưa đủ
		for (int i = 0; i < numEdges[v]; i++) {
			if (visited[next[v][i]] > 0) {
				if (visited[next[v][i]] < count) { // không thể tính trường hợp = vì nó có thể tính lại đỉnh trước
					found = true;
					return;
				}
				continue;
// không thực hiện DFS bên dưới, tiếp tục tìm các đỉnh kề có lượt visit > 0
			}

			// đánh dấu nhánh theo chiều sâu với giá trị count
			visited[next[v][i]] = count;
			DFS(from, next[v][i]);

		}
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class DiAnCuoi_2 {
	static int N, M;
	static int[][] graph;
	static int[] degree;
	static int count;
	static int[] visit1 = new int[21];
	static int[] visit2 = new int[21];
	static int minVertex;

	public static void backTrack2(int vertex, int count) {
		if (count > minVertex) {
			return;
		}
		if (vertex == 1) {
			minVertex = Math.min(minVertex, count);
			return;
		}
		for (int i = 0; i < degree[vertex]; i++) {
			int next = graph[vertex][i];
			if (visit2[next] == 0) { // chua duoc xet o luot ve
				visit2[next] = 1;
				if (visit1[next] == 0) {
					backTrack2(next, count + 1);
				} else {
					backTrack2(next, count);
				}
				visit2[next] = 0;
			}
		}
	}

	public static void backTrack1(int vertex, int count) {
		if (count > minVertex) {
			return;
		}
		if (vertex == 2) {
			backTrack2(2, count);
			return;
		}
		for (int i = 0; i < degree[vertex]; i++) {
			int next = graph[vertex][i];
			if (visit1[next] == 0) {
				visit1[next] = 1;
				backTrack1(next, count + 1);
				visit1[next] = 0;
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\DiAnCuoi_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			degree = new int[21];
			graph = new int[21][21];
			for (int i2 = 0; i2 < M; i2++) {
				int u = sc.nextInt();
				int v = sc.nextInt();
				graph[u][degree[u]++] = v;
			}
			minVertex = Integer.MAX_VALUE;
			visit1[1] = 1;
			visit2[2] = 1;
			backTrack1(1, 1);
			System.out.println(minVertex);
		}
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class FindCycle_DFS {
	static int V; // Số đỉnh
	static int E; // Số cạnh
	static int[][] adj; // Ma trận kề
	static boolean[] visited; // Mảng đánh dấu các đỉnh đã duyệt

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\FindCycle_input.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			V = scanner.nextInt();
			E = scanner.nextInt();
			adj = new int[V][V];
			for (int i = 0; i < E; i++) {
				int u = scanner.nextInt() - 1;
				int v = scanner.nextInt() - 1;
				adj[u][v] = 1;
			}
			visited = new boolean[V];
			boolean hasCycle = false;
			for (int i = 0; i < V; i++) {
				if (isCyclic(i)) {
					hasCycle = true;
					break;
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(hasCycle ? 1 : 0);
		}
		scanner.close();
	}

	private static boolean isCyclic(int v) {
		if (visited[v]) {
			return true;
		}
		visited[v] = true;
		for (int u = 0; u < V; u++) {
			if (adj[v][u] == 1 && isCyclic(u)) {
				return true;
			}
		}
		// buộc phải có dòng code hoàn nguyên sau ???
		// Lưu ý đây là đồ thị có hướng nên cần phải hoàn nguyên visited[v] = false
		visited[v] = false;
		return false;
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Maze2_DFS {
	static int startX, startY, endX, endY;
	static int[][] maze;
	static boolean[][] visited;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, -1, 0, 1 };
	static boolean found;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\Maze2_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		while (T-- > 0) {
			int tc = sc.nextInt();
			maze = new int[100][100];
			for (int i = 0; i < 100; i++) {
				String line = sc.next();
				for (int j = 0; j < 100; j++) {
					maze[i][j] = line.charAt(j) - '0';
				}
			}
			for (int i = 0; i < 100; i++) {
				for (int j = 0; j < 100; j++) {
					if (maze[i][j] == 2) {
						startX = i;
						startY = j;
					} else if (maze[i][j] == 3) {
						endX = i;
						endY = j;
					}
				}
			}
			visited = new boolean[100][100];
			found = false;
			DFS(startX, startY);
			if (found) {
				System.out.println("#" + tc + " " + 1);
			} else {
				System.out.println("#" + tc + " " + 0);
			}

		}
	}

// DFS này không cần gỡ đánh dấu
	public static void DFS(int x, int y) {
		if (found) {
			return;
		}
		if (x == endX && y == endY) {
			found = true;
			return;
		}
		visited[x][y] = true;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < 100 && ny < 100 && !visited[nx][ny] && maze[nx][ny] != 1) {
				DFS(nx, ny);
			}
		}
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

public class Maze2 {
	static int startX, startY, endX, endY;
	static int[][] maze;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\Maze2_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		while (T-- > 0) {
			int tc = sc.nextInt();
			maze = new int[100][100];
			for (int i = 0; i < 100; i++) {
				String line = sc.next();
				for (int j = 0; j < 100; j++) {
					maze[i][j] = line.charAt(j) - '0';
				}
			}
			for (int i = 0; i < 100; i++) {
				for (int j = 0; j < 100; j++) {
					if (maze[i][j] == 2) {
						startX = i;
						startY = j;
					} else if (maze[i][j] == 3) {
						endX = i;
						endY = j;
					}
				}
			}
			System.out.println("#" + tc + " " + hasPath());
		}
	}

	public static int hasPath() {
		boolean[][] visited = new boolean[100][100];
		Stack<int[]> stack = new Stack<>();
		stack.push(new int[] { startX, startY });
		while (!stack.isEmpty()) {
			int[] pos = stack.pop();
			int x = pos[0];
			int y = pos[1];
			if (x == endX && y == endY) {
				return 1;
			}
			visited[x][y] = true;

			// kiem tra cac o xung quanh, de luu duong di
			// lưu ý để == 0 là sai vì các điểm 3 cũng cần được xét
			if (x > 0 && !visited[x - 1][y] && maze[x - 1][y] != 1) {
				stack.push(new int[] { x - 1, y });
			}
			if (x <= 98 && !visited[x + 1][y] && maze[x + 1][y] != 1) {
				stack.push(new int[] { x + 1, y });
			}
			if (y > 0 && !visited[x][y - 1] && maze[x][y - 1] != 1) {
				stack.push(new int[] { x, y - 1 });
			}
			if (y <= 98 && !visited[x][y + 1] && maze[x][y + 1] != 1) {
				stack.push(new int[] { x, y + 1 });
			}

		}
		return 0;
	}

	public static void print(int[][] maze) {
		for (int i = 0; i < maze.length; i++) {
			for (int j = 0; j < maze[0].length; j++) {
				System.out.print(maze[i][j]);
			}
			System.out.println();
		}
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MoiDamCuoi {
	static int N, M, u, v, Answer, countWay;
	static boolean[] visit;
	static int[] countVisited;
	static int[][] adjMatrix;

	public static void DFS(int x) {
		if (x == v) {
			countWay++;
			// tăng chỉ số xuất hiện cho tất cả các điểm xuất hiện trên đường đi
			for (int i = 1; i <= N; i++) {
				if (visit[i])
					countVisited[i]++;
			}
			return;
		}
		for (int i = 0; i < adjMatrix[x][0]; i++) {
			if (!visit[adjMatrix[x][i + 1]]) {
				visit[adjMatrix[x][i + 1]] = true;
				DFS(adjMatrix[x][i + 1]);
				visit[adjMatrix[x][i + 1]] = false;
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\MoiDamCuoi_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; ++tc) {
			Answer = 0;
			N = sc.nextInt(); // số đỉnh - tối đa 100
			M = sc.nextInt(); // số cạnh - tối đa 1000
			u = sc.nextInt(); // điểm xuất phát
			v = sc.nextInt(); // điểm kết thúc
			adjMatrix = new int[101][1001];
			for (int i = 0; i < M; i++) {
				int d1 = sc.nextInt();
				int d2 = sc.nextInt();
				adjMatrix[d1][0]++;
				adjMatrix[d1][adjMatrix[d1][0]] = d2;
			}
			visit = new boolean[101]; // đánh dấu, hỗ trợ DFS, BFS
			// đếm số lần xuất hiện trên tất cả các đường từ u tới v
			countVisited = new int[101];
			visit[u] = true;
			countWay = 0; // đếm số đường đi từ u tới v

			DFS(u);
			for (int i = 1; i <= N; i++) {
				if (i != u && i != v && countVisited[i] == countWay) {
					Answer++;
				}
			}
			System.out.println(Answer);
			System.out.println();
			System.out.println();
		}
	}
}

package DFS;

// đồ thị có hướng
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class RouteFinding_DFS {
	static int N;
	static boolean[][] graph;
	static boolean[] visited;
	static boolean found;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\RouteFinding_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		while (T-- > 0) {
			int tc = sc.nextInt();
			System.out.print("#" + tc + " ");
			N = sc.nextInt();
			graph = new boolean[101][101];

			for (int i = 0; i < N; i++) {
				int from = sc.nextInt();
				int to = sc.nextInt();
				graph[from][to] = true;
			}
			visited = new boolean[100];
			found = false;
			DFS(0);
			if (found) {
				System.out.print(1);
			} else {
				System.out.print(0);
			}
			System.out.println();
		}
	}

	static void DFS(int x) {
		if (found) {
			return;
		}
		if (x == 99) {
			found = true;
			return;
		}
		visited[x] = true;
		for (int i = 0; i < 100; i++) {
			if (graph[x][i] && !visited[i]) {
				DFS(i);
			}
		}
	}
}

package DFS;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

public class RouteFinding {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\DFS\\RouteFinding_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		while (T-- > 0) {
			int tc = sc.nextInt();
			System.out.print("#" + tc + " ");
			int N = sc.nextInt();
			boolean[][] graph = new boolean[101][101];

			for (int i = 0; i < N; i++) {
				int from = sc.nextInt();
				int to = sc.nextInt();
				graph[from][to] = true;
			}
			Stack<Integer> stack = new Stack<>();
			boolean[] visited = new boolean[101];
			stack.push(0);
			visited[0] = true;
			boolean found = false;
			while (!stack.isEmpty()) {
				int current = stack.pop();
				if (current == 99) {
					System.out.print(1);
					found = true;
					break;
				}
				for (int i = 0; i < 100; i++) {
					if (graph[current][i] && !visited[i]) {
						visited[i] = true;
						stack.push(i);
					}
				}
			}
			if (!found) {
				System.out.print(0);
			}
			System.out.println();
		}
	}
}

package Recursion;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class CuttingPaper {
	static int[][] paper;
	static int countWhite, countBlue;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Recursion\\CuttingPaper_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt();
			paper = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					paper[i][j] = sc.nextInt();
				}
			}
			countWhite = 0;
			countBlue = 0;
			cut(0, 0, N);
			System.out.println("Case #" + tc);
			System.out.println(countWhite + " " + countBlue);
		}

	}

	public static void cut(int startX, int startY, int N) {
		if (isWhite(startX, startY, N)) {
			countWhite++;
		} else if (isBlue(startX, startY, N)) {
			countBlue++;
		} else {
			cut(startX, startY, N / 2);
			cut(startX + N / 2, startY, N / 2);
			cut(startX, startY + N / 2, N / 2);
			cut(startX + N / 2, startY + N / 2, N / 2);
		}

	}

	public static boolean isBlue(int startX, int startY, int size) {
		for (int i = startX; i < startX + size; i++) {
			for (int j = startY; j < startY + size; j++) {
				if (paper[i][j] == 0) { // ton tai o trang
					return false;
				}
			}
		}
		return true;
	}

	public static boolean isWhite(int startX, int startY, int size) {
		for (int i = startX; i < startX + size; i++) {
			for (int j = startY; j < startY + size; j++) {
				if (paper[i][j] == 1) { // ton tai o xanh
					return false;
				}
			}
		}
		return true;
	}
}

package Recursion;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class GameWithNumbers_DeQuy {
	static int N;
	static int[] arr;
	static int[][] hardScore, easyScore;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Recursion\\GameWithNumbers_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			arr = new int[N];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = sc.nextInt();
			}
			hardScore = new int[N][N];
			easyScore = new int[N][N];
			System.out.println("Case #" + tc);
			System.out.println(EasyScore(0, N - 1) + " " + HardScore(0, N - 1));
		}
	}

	public static int HardScore(int i, int j) {

		if (i > j) {
			return 0;
		}
		// if (i + 1 == j) {
		// return Math.max(arr[i], arr[j]);
		// }
		// dynamic programming - memoization
		if (hardScore[i][j] != 0) {
			return hardScore[i][j];
		}
		return hardScore[i][j] = Math.max(arr[i] + Math.min(HardScore(i + 2, j), HardScore(i + 1, j - 1)),
				arr[j] + Math.min(HardScore(i + 1, j - 1), HardScore(i, j - 2)));
	}

	public static int EasyScore(int i, int j) {
		if (i > j) {
			return 0;
		}
		// if (i + 1 == j) {
		// return Math.max(arr[i], arr[j]);
		// }
		// dynamic programming - memoization
		if (easyScore[i][j] != 0) {
			return easyScore[i][j];
		}
		return easyScore[i][j] = Math.max(arr[i] + Math.max(EasyScore(i + 2, j), EasyScore(i + 1, j - 1)),
				arr[j] + Math.max(EasyScore(i + 1, j - 1), EasyScore(i, j - 2)));
	}
}

package Recursion;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

// Chia De Tri
public class MatrixProduct {
	static int N, M;
	static long[][] matrix;
	static long[][] result;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Recursion\\MatrixProduct_input2.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			matrix = new long[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			result = new long[N][N];
			result = matrixPower(matrix, M);
			System.out.println("Case #" + tc);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					System.out.print(result[i][j] + " ");
				}
				System.out.println();
			}

		}
	}

	public static long[][] matrixPower(long[][] A, int M) {
		// base condition
		if (M == 1) {
			return A;
		}
		long[][] result2 = matrixPower(A, M / 2);
		result2 = matrixMultiply(result2, result2);
		if (M % 2 == 1) {
			result2 = matrixMultiply(result2, A);
		}
		return result2;
	}

	public static long[][] matrixMultiply(long[][] A, long[][] B) {
		long[][] result2 = new long[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) {
					result2[i][j] = (result2[i][j] + (A[i][k] * B[k][j]) % 100000007) % 100000007;
				}
			}
		}
		return result2;
	}
}

package Recursion;

// GREEDY
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Partition1_Cach1 {
	static int Cost = 0;
	static int Answer = 0;
	static int N;
	static int[] arr;

	// sap xep tang dan
	static int[] SortTangDan(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i; // minIndex
			for (int j = i + 1; j < arr.length; j++)
				if (arr[j] < arr[minIndex])
					minIndex = j;

			int temp = arr[minIndex];
			arr[minIndex] = arr[i];
			arr[i] = temp;
		}
		return arr;
	}

// điểm dừng là 1 vì không có mảng rỗng trong thuật toán
// khi gọi đến mảng còn 1 phần tử thì trước đó đã cộng phần tử cuối đó vào cost rồi
	static void Cal(int[] arr, int N) {

		if (N == 1) {
			return;
		}
		// sap xep tang dan
		arr = SortTangDan(arr);
		arr[1] += arr[0]; // cộng 2 số nhỏ nhất ở cuối, dồn vào index 1

		int[] newPartition = new int[N - 1];
		// clone tu partition cu sang partiotion moi
		for (int i = 1; i < N; i++) {
			newPartition[i - 1] = arr[i];
		}
		Cost += newPartition[0];
		Cal(newPartition, N - 1); // goi ham de quy
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Recursion\\Partition1_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			arr = new int[N];
			Cost = 0;
			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
			}
			Cal(arr, N);
			System.out.println("Case #" + tc);
			System.out.println(Cost);
		}
	}
}

package Other;

// GREEDY
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class AssigningMeetingRoom {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\AssigningRoom_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt();
			int[] numMeeting = new int[N];
			int[] startTime = new int[N];
			int[] endTime = new int[N];
			for (int i = 0; i < N; i++) {
				numMeeting[i] = sc.nextInt();
				startTime[i] = sc.nextInt();
				endTime[i] = sc.nextInt();
			}
			// khi sắp xếp mảng là theo thời gian kết thúc
			// khi đếm meeting là theo thời gian bắt đầu
			for (int i = 0; i < N - 1; i++) { // N-1 luot sap xep
				for (int j = i + 1; j < N; j++) {
					// sap xep thoi gian ket thuc, som nhat cho len truoc
					if (endTime[i] > endTime[j]) {
						int temp = endTime[i];
						endTime[i] = endTime[j];
						endTime[j] = temp;

						temp = startTime[i];
						startTime[i] = startTime[j];
						startTime[j] = temp;
						// Cach dao 2
					}
				}
			}
			int Answer = 0;
			int lastTime = 0; // thoi gian bat dau to chuc cuoc hop cuoi cung

			for (int i = 0; i < N; i++) {
				if (startTime[i] >= lastTime) {
					Answer++;
					lastTime = endTime[i];
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(Answer);
		}
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Crossroads {
	static int N;
	static int[][] map1 = new int[100][100], map2 = new int[100][100];

	static void updateMap() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (map1[i][j] != map2[i][j])
					map1[i][j] = map2[i][j];
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Adv2018\\Crossroads_input.txt"));
		Scanner sc = new Scanner(System.in);
		int year = 0, x, y;
		N = sc.nextInt();
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				map1[i][j] = sc.nextInt();
				map2[i][j] = map1[i][j];
			}
		}
		boolean found = true;
		while (found) {
			found = false;
			for (int i = 2; i < N; i++) {
				for (int j = 2; j < N; j++) {

					if (map1[i][j] == 0 && (map1[i + 1][j] + map1[i - 1][j] + map1[i][j - 1] + map1[i][j + 1]) == 1) {

						found = true;
						if (map1[i + 1][j] == 1) {
							x = i;
							y = j;
							while (map1[++x][y] == 1 && x <= N)
								map2[x][y] = 0;
						} else if (map1[i - 1][j] == 1) {
							x = i;
							y = j;
							while (map1[--x][y] == 1 && x >= 1)
								map2[x][y] = 0;
						} else if (map1[i][j + 1] == 1) {
							x = i;
							y = j;
							while (map1[i][++y] == 1 && y <= N)
								map2[x][y] = 0;
						} else if (map1[i][j - 1] == 1) {
							x = i;
							y = j;
							while (map1[i][--y] == 1 && y >= 1)
								map2[x][y] = 0;
						}
					}
				}
			}
			if (found)
				year++;
			updateMap();
		}
		System.out.println(year);
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class DaoCot {
	static int N, M, K;
	static int[][] matrix;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\DaoCot_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			K = sc.nextInt();
			matrix = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			System.out.println("Case #" + tc + " " + maxEqualRowsAfterFlips());
		}
	}

	public static int maxEqualRowsAfterFlips() {
		int maxRows = 0;
		for (int i = 0; i < N; i++) {
			// dem co bao nhieu so 0 --> bao nhieu lan can dao cot
			int[] row = matrix[i];
			int flipsNeeded = 0;
			for (int j = 0; j < M; j++) {
				if (row[j] == 0) {
					flipsNeeded++;
				}
			}
			if (flipsNeeded <= K && (K - flipsNeeded) % 2 == 0) {
				int rowsWithAllOnes = 0;
				for (int l = 0; l < N; l++) {
					boolean allOnes = true;
					for (int j = 0; j < M; j++) {
						if (row[j] != matrix[l][j]) {
							allOnes = false;
							break;
						}
					}
					if (allOnes) {
						rowsWithAllOnes++;
					}
				}
				maxRows = Math.max(maxRows, rowsWithAllOnes);
			}
		}
		return maxRows;
	}

}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Earning_Optimal1 {
	static int max = 0;
	static int[] arr;
	static int[] temp;
	static int n;
	static int k;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\EarningBiggestMoney_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			String s = sc.next();
			n = s.length();
			arr = new int[n];
			temp = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = s.charAt(i) - '0';
				temp[i] = arr[i];
			}
			k = sc.nextInt();
			max = Integer.MIN_VALUE;
			greedy(0, k);
			System.out.println("Case #" + t);
			System.out.println(max);
		}
	}

	public static void greedy(int start, int k) {
		if (k == 0) {
			max = Math.max(max, toInt(temp));
			return;
		}
		for (int i = start; i < n; i++) {
			int maxIndex = i;
			for (int j = i + 1; j < n; j++) {
				if (temp[j] > temp[maxIndex]) {
					maxIndex = j;
				}
			}
			// có nhiều số lớn nhất - sinh hoán vị tất
			for (int j = i + 1; j < n; j++) {
				if (temp[j] == temp[maxIndex] && j != i) {
					swap(i, j);
					greedy(i + 1, k - 1);
					swap(i, j);
				}
			}
		}
		if (k > 0) { // nếu đã hoán vị hết với các số lớn nhất mà k vẫn chưa về 0
			if (hasDuplicate(temp) || k % 2 == 0) {
				max = Math.max(max, toInt(temp));
				return;
			} else if (k % 2 == 1) {
				swap(n - 2, n - 1);
				max = Math.max(max, toInt(temp));
				swap(n - 2, n - 1);
				return;
			}
		}
	}

	public static boolean hasDuplicate(int[] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = i + 1; j < a.length; j++) {
				if (a[i] == a[j]) {
					return true;
				}
			}
		}
		return false;
	}

	public static void swap(int i, int j) {
		int t = temp[i];
		temp[i] = temp[j];
		temp[j] = t;
	}

	public static int toInt(int[] a) {
		int res = 0;
		for (int i : a) {
			res *= 10;
			res += i;
		}
		return res;
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Earning_Optimal2 {
	static int max = 0;
	static int[] arr;
	static int[] temp;
	static int n;
	static int k;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\EarningBiggestMoney_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			String s = sc.next();
			n = s.length();
			arr = new int[n];
			temp = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = s.charAt(i) - '0';
				temp[i] = arr[i];
			}
			k = sc.nextInt();
			max = Integer.MIN_VALUE;
			greedy(0, k);
			System.out.println("Case #" + t);
			System.out.println(max);
		}
	}

	public static void greedy(int start, int k) {
		if (k == 0) {
			max = Math.max(max, toInt(temp));
			return;
		}
		for (int i = start; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (temp[j] > temp[i]) {
					swap(i, j);
					greedy(i + 1, k - 1);
					swap(i, j);
				}
			}
		}
		if (k > 0) {
			if (hasDuplicate(temp) || k % 2 == 0) {
				max = Math.max(max, toInt(temp));
				return;
			} else if (k % 2 == 1) {
				swap(n - 2, n - 1);
				max = Math.max(max, toInt(temp));
				swap(n - 2, n - 1);
				return;
			}
		}
	}

	public static boolean hasDuplicate(int[] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = i + 1; j < a.length; j++) {
				if (a[i] == a[j]) {
					return true;
				}
			}
		}
		return false;
	}

	public static void swap(int i, int j) {
		int t = temp[i];
		temp[i] = temp[j];
		temp[j] = t;
	}

	public static int toInt(int[] a) {
		int res = 0;
		for (int i : a) {
			res *= 10;
			res += i;
		}
		return res;
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Earning_Optimal3 {
	static int T, changes, len, Anwser, value;
	static char[] number = new char[10];
	static boolean[][] visited = new boolean[11][1000000];
	static char[] permuteNum = new char[10];
	static char temp;

// đánh dấu hoán vị đã duyệt tới chưa
// 1d = số lần đảo, 2d = cận max

	// k = lượt đảo
	static void sinhHoanVi(int k, char[] num) {

		// chuyển sang giá trị integer
		value = 0;
		for (int l = 0; l < len; l++) {
			value = value * 10 + num[l] - 48; // 48 = '0'
		}

		if (visited[k][value]) {
			return;
		}
		visited[k][value] = true;

//		char[] permuteNum = new char[10];
//		char temp;

		if (k == changes) {
			Anwser = value > Anwser ? value : Anwser;
			return;
		}
		for (int i = 0; i <= len - 2; i++) {
			for (int j = i + 1; j <= len - 1; j++) {
				for (int l = 0; l < len; l++) {
					permuteNum[l] = num[l];
				}
				temp = permuteNum[i];
				permuteNum[i] = permuteNum[j];
				permuteNum[j] = temp;
				sinhHoanVi(k + 1, permuteNum);
			}
		}

	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\EarningBiggestMoney_input.txt"));
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			number = sc.next().toCharArray();
			changes = sc.nextInt();
			len = number.length;

			// tính giá trị cận max của mọi hoán vị
			int maxValue = 1;
			for (int i = 1; i <= len; i++) {
				maxValue *= 10;
			}

			// reset lại mảng visit sau mỗi testcase
			for (int i = 0; i < changes; i++) {
				for (int j = 0; j < maxValue; j++) {
					if (visited[i][j])
						visited[i][j] = false;
				}
			}
			Anwser = 0;
			sinhHoanVi(0, number);
			System.out.println("Case #" + tc);
			System.out.println(Anwser);
		}
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class EarningBiggestMoney_SapXep {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\EarningBiggestMoney_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			String number = sc.next();
			int numExchange = sc.nextInt();
			int K = numExchange;
			char[] arr = number.toCharArray();
			int len = arr.length;
			for (int i = 0; i <= len - 2 && numExchange > 0; i++) {
				int maxIndex = findMaxInRange(arr, i, len - 1);
				if (maxIndex != i && arr[i] != arr[maxIndex]) {
					char temp = arr[i];
					arr[i] = arr[maxIndex];
					arr[maxIndex] = temp;
					--numExchange;
				}
				// System.out.println(new String(arr) + " / " + numExchange);
			}
			// System.out.println(numExchange);
			if (numExchange > 0) {
				if (!checkDuplicate(arr)) {
					if (numExchange % 2 == 1) {
						char temp = arr[len - 1];
						arr[len - 1] = arr[len - 2];
						arr[len - 2] = temp;
					}
				}
			}
			String num = new String(arr);
			int res = Integer.parseInt(num);
			System.out.println("Case #" + tc);
			System.out.println(res);

		}
	}

	public static boolean checkDuplicate(char[] num) {
		for (int i = 0; i < num.length; i++) {
			for (int j = i + 1; j < num.length; j++) {
				if (num[i] == num[j]) {
					return true;
				}
			}
		}
		return false;
	}

	public static int findMaxInRange(char[] arr, int i, int j) {
		int max = Integer.MIN_VALUE;
		int maxIndex = i;
		for (int k = i; k <= j; k++) {
			if (arr[k] > max) { // >=
				max = arr[k];
				maxIndex = k;
			}
		}
		return maxIndex;
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class LuckyNumber_Cach1 {
	static final int N = 205;
	static int T, n;
	static int[][] f = new int[N][N];
	static int[] p10 = new int[N];

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\LuckyNumber_input.txt"));
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt(); // so X can chia het
			for (int i = 0; i <= 200; i++) {
				// Arrays.fill(f[i], -1);
				for (int j = 0; j < f[i].length; j++) {
					f[i][j] = -1;
				}
			}
			p10[0] = 1;
			for (int i = 1; i <= 200; i++) {
				p10[i] = p10[i - 1] * 10 % n;
			}
			// Queue<int[]> st = new LinkedList<>();
			Queue queue = new Queue(2000);
			queue.add(new int[] { 0, 1 });
			f[0][1] = 6 % n;
			queue.add(new int[] { 1, 0 });
			f[1][0] = 8 % n;
			boolean found = false;
			while (!queue.isEmpty()) {
				int x = queue.front()[0], y = queue.front()[1];
				queue.poll();
				if (f[x][y] == 0) {
					System.out.println("Case #" + tc);
					for (int i = 1; i <= x; i++) {
						System.out.print("8");
					}
					for (int i = 1; i <= y; i++) {
						System.out.print("6");
					}
					System.out.println();
					found = true;
					break;
				}
				if (x + y == 200) {
					continue;
				}
				if (f[x][y + 1] == -1) {
					f[x][y + 1] = (f[x][y] * 10 % n + 6) % n;
					queue.add(new int[] { x, y + 1 });
				}
				if (f[x + 1][y] == -1) {
					f[x + 1][y] = (8 * p10[x + y] % n + f[x][y]) % n;
					queue.add(new int[] { x + 1, y });
				}
			}
			if (!found) {
				System.out.println("Case #" + tc);
				System.out.println("-1");
			}
		}
	}
}

package Other;

// Chia De Tri va Binary Search, co the dung Dynamic Programming
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MinBigSum {
	static int K, N;
	static int[] arr;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\MinBigSum_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			K = sc.nextInt();
			N = sc.nextInt();
			arr = new int[N];
			int start = 0;
			int end = 0;
			int Ans = 0;
			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
				end += arr[i];
				start = Math.max(start, arr[i]);
			}

			while (start <= end) {
				int sum = 0;
				int count = 0;
				int mid = (start + end) / 2; // test
				// System.out.println(mid);
				for (int i = 0; i < N; i++) {
					sum += arr[i];
					// chia các khoảng nhỏ hơn hoặc bằng mid
					if (sum > mid) {
						count++;
						sum = arr[i];
					}
				}
				if (count < K) {
					// duyet phan duoi cua mid
					Ans = mid;
					end = mid - 1;
				} else {
					start = mid + 1;
				}
			}
			System.out.println("#" + tc + " " + Ans);
		}

	}

}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

// duyet tu day nhich len 
public class MinBigSum_Cach2 {
	static int K, N;
	static int[] arr;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\MinBigSum_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			K = sc.nextInt();
			N = sc.nextInt();
			arr = new int[N];
			int start = 0;
			int end = 0;
			int Ans = 0;
			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
				end += arr[i];
				start = Math.max(start, arr[i]);
			}
			while (start <= end) {
				int sum = 0;
				int count = 0;
				for (int i = 0; i < N; i++) {
					sum += arr[i];
					if (sum > start) {
						count++;
						sum = arr[i];
					}
				}
				if (count < K) {
					Ans = start;
					break;
				} else {
					start++;
				}
			}
			System.out.println("#" + tc + " " + Ans);
		}
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class PointOfBalance_Cach1 {
	static double F1, F2;
	static double testPoint;
	static int[] mass, toado;
	static int N;
	static double[] DapAn;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\PointOfBalance_input.txt"));
		Scanner sc = new Scanner(System.in);
		int tc = 1;
		int T = 10;
		while (T-- > 0) {
			N = sc.nextInt();
			toado = new int[N];
			mass = new int[N];
			for (int i = 0; i < N; i++) {
				toado[i] = sc.nextInt();
			}
			for (int i = 0; i < N; i++) {
				mass[i] = sc.nextInt();
			}
			DapAn = new double[10];
			for (int i = 0; i <= N - 2; i++) {
				FindBalance(toado[i], toado[i + 1], i);
			}

			System.out.print("#" + tc + " ");
			for (int i = 0; i <= N - 2; i++) {
				System.out.printf("%.10f", DapAn[i]);
				System.out.print(" ");
			}
			System.out.println();
			tc++;
		}
	}

	public static void FindBalance(double left, double right, int i) {
		F1 = 0.0; // luc ben trai tac dong
		F2 = 0.0; // luc ben phai tac dong

		double distance = 1.0; // khoang cach giua 2 diem - se thu hep dan
		testPoint = (left + right) / 2; // left la toado[i], right la toado[i+1]
		for (int j = 0; j <= i; j++) {
			F1 = F1 + mass[j] / ((testPoint - toado[j]) * (testPoint - toado[j]));
		}
		for (int j = N - 1; j > i; j--) {
			F2 = F2 + mass[j] / ((testPoint - toado[j]) * (testPoint - toado[j]));
		}
// nếu lực bên trái lớn hơn --> checkPoint dịch về phải
		if (F1 > F2) {
			distance = right - left; // right luôn lớn hơn left
			left = testPoint;
			// đệ quy để thu hẹp khoảng cách, cách khác là dùng vòng while
			if (distance >= 0.0000000001) { // sai số lớn hơn cho phép
				FindBalance(left, right, i);
			} else {
				DapAn[i] = testPoint;
			}
		} else if (F2 > F1) {
			distance = right - left;
			right = testPoint;
			if (distance >= 0.0000000001) {
				FindBalance(left, right, i);
			} else {
				DapAn[i] = testPoint;
			}
		} else {
			DapAn[i] = testPoint;
		}
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class PointOfBalance_Cach2 {
	static double F1, F2;
	static double testPoint;
	static int[] mass, toado;
	static int N;
	static double[] DapAn;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\PointOfBalance_input.txt"));
		Scanner sc = new Scanner(System.in);
		int tc = 1;
		int T = 10;
		while (T-- > 0) {
			N = sc.nextInt();
			toado = new int[N];
			mass = new int[N];
			for (int i = 0; i < N; i++) {
				toado[i] = sc.nextInt();
			}
			for (int i = 0; i < N; i++) {
				mass[i] = sc.nextInt();
			}
			DapAn = new double[10];
			for (int i = 0; i <= N - 2; i++) {
				FindBalance(toado[i], toado[i + 1], i);
			}

			System.out.print("#" + tc + " ");
			for (int i = 0; i <= N - 2; i++) {
				// System.out.print(DapAn[i] + " ");
				System.out.printf("%.10f", DapAn[i]);
				System.out.print(" ");
			}
			System.out.println();
			tc++;
		}
	}

	public static void FindBalance(double left, double right, int i) {
		double distance = 1.0; // khoang cach giua 2 diem - se thu hep dan
		while (distance >= 0.0000000001) {
			F1 = 0.0; // luc ben trai tac dong
			F2 = 0.0; // luc ben phai tac dong

			// left là toado[i], right là toado[i+1]
			testPoint = (left + right) / 2;
			DapAn[i] = testPoint;
			for (int j = 0; j <= i; j++) {
				F1 = F1 + mass[j] / ((testPoint - toado[j]) * (testPoint - toado[j]));
			}
			for (int j = N - 1; j > i; j--) {
				F2 = F2 + mass[j] / ((testPoint - toado[j]) * (testPoint - toado[j]));
			}
			if (F1 == F2) {
				break;
			} else if (F1 > F2) {
				distance = right - left;
				left = testPoint;
			} else {
				distance = right - left;
				right = testPoint;
			}
		}

	}
}

package Other;

import java.util.Scanner;

public class PriceTag {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			int N = sc.nextInt();
			int[][] square = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					square[i][j] = sc.nextInt();
				}
			}
			int maxSum = 0;
			for (int i = 0; i < N; i++) {
				int sum = 0;
				for (int j = 0; j < N; j++) {
					sum += square[i][j] * Math.pow(10, N - j - 2);
				}
				maxSum = Math.max(maxSum, sum);
			}
			for (int j = 0; j < N; j++) {
				int sum = 0;
				for (int i = 0; i < N; i++) {
					sum += square[i][j] * Math.pow(10, N - i - 2);
				}
				maxSum = Math.max(maxSum, sum);
			}
			System.out.println("#" + t + " " + maxSum);
		}
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class TanCongThanhTri_Prim {

	static int M, Answer, u, v, total, remain;
	static int[] key, parent, value, count; // count[u] là số cạnh của đỉnh u
	static int[][] graph, adjList;
	static boolean[] visited;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\TanCongThanhTri_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			M = sc.nextInt();
			key = new int[M + 1];
			parent = new int[M + 1];
			value = new int[M + 1];
			graph = new int[M + 1][M + 1];
			count = new int[M + 1];
			adjList = new int[M + 1][M + 1];
			total = 0; // tong so may ban da
			for (int i = 0; i < M; i++) { // thong tin cua moi dinh
				int idx = sc.nextInt();
				value[idx] = sc.nextInt(); // so may ban da
				count[idx] = sc.nextInt(); // số cạnh của đỉnh idx
				for (int j = 0; j < count[idx]; j++) {
					int next = sc.nextInt(); // cac thanh tri
					graph[idx][next] += value[idx];
					graph[next][idx] += value[idx];
					total += value[idx];
					adjList[idx][j] = next;
				}
			}

			u = 0;
			visited = new boolean[M];
			for (int i = 0; i < M; i++) {
				key[i] = Integer.MIN_VALUE;
				parent[i] = -1;
			}
			key[0] = 0;
// key[0] là điểm ban đầu, lớn hơn mọi đỉnh còn lại là min_value
// tìm cây khung lớn nhất nên cắm key max
// key[v] có giá trị là cạnh lớn nhất của v
			for (int i = 0; i <= M - 2; i++) { // M-2 lượt cắm và update key
				u = findMax();
				visited[u] = true;
				for (int j = 0; j < count[u]; j++) {
					v = adjList[u][j];
					if (!visited[v] && graph[u][v] > key[v]) {
						key[v] = graph[u][v];
						parent[v] = u;
					}
				}
//				if (u != -1) { // gap truong hop nay khi trong do thi co
//					// nhieu
//					// thanh phan, u se tra ve 0 khi duyet het cac
//					// diem cua 1 thanh phan
//					visited[u] = true;
//					for (int j = 0; j < count[u]; j++) {
//						v = adjList[u][j];
//						if (!visited[v] && graph[u][v] > key[v]) {
//							key[v] = graph[u][v];
//							parent[v] = u;
//						}
//					}
//				} else {
//					int k;
//					for (k = 0; k < M; k++) { // tim diem chua duoc tham cua
//						// thanh phan con lai, gan key 0
//						// de duyet tu diem do
//						if (!visited[k])
//							break;
//					}
//					key[k] = 0;
//					i--; // dung de duyet lai luot nay
//				}
			}
			remain = 0;
			for (int i = 0; i <= M - 1; i++) {
				if (parent[i] != -1) { // quan trọng, chỉ xét các đỉnh có parent
					remain += graph[i][parent[i]];
				}
			}
			System.out.println(total - remain);
		}
	}

	public static int findMax() {
		int maxIndex = -1;
		int Max = Integer.MIN_VALUE;
		for (int v = 0; v < M; v++) {
			if (!visited[v] && key[v] >= Max) {
				Max = key[v];
				maxIndex = v;
			}
		}
		return maxIndex;
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class TanCongThanhTri_DFS {
	static final int max_size = 105;
	static final int vc = 1000000;
	static int[] mayBD;
	static int[][] A;
	static int[] visit;
	static int n;
	static int ans;
	static boolean flag;

	static void reset() { // Reset de dfs
		for (int i = 0; i < n; i++)
			visit[i] = 0;
	}

// tempThanh: thành đang xét
// thành: đích
// sl: số lượng đỉnh đã được duyệt qua
// tempMin: số lượng máy bắn đá ít nhất cần sử dụng để phá hủy thành lũy hiện tại
// d1, d2: 2 đầu của cạnh cần phá
	static void dfs(int tempThanh, int thanh, int sl, int tempMin, int d1, int d2) {
		if (tempThanh == thanh && sl >= 3) { // muốn có chu trình thì số lượng đỉnh đã đi qua >= 3
			flag = true; // nghĩa là có chu trình để diệt
			ans += tempMin;
			A[d1][d2] = 0;
			A[d2][d1] = 0;
			return;
		}
		for (int col = 0; col < n; col++) { // duyệt các đỉnh kề
			if (flag) // đã tìm thấy thì ngừng
				return;
			if (A[tempThanh][col] == 1 && (visit[col] == 0 || (col == thanh && sl >= 3))) {
				visit[col] = 1;
				int value = mayBD[tempThanh] + mayBD[col];
				if (tempMin > value) {
					dfs(col, thanh, sl + 1, value, tempThanh, col);
				} else {
					dfs(col, thanh, sl + 1, tempMin, d1, d2);
				}
			}
		}
	}

	static void solve() {
		// duyệt n thành để đảm bảo phá hủy hết các phần rời rạc của đồ thị
		// từ mỗi đỉnh dfs để tìm cạnh cần phá
		for (int thanh = 0; thanh < n; thanh++) {
			reset();
			visit[thanh] = 1;
			flag = false; // nếu tìm thấy cạnh để phá , flag sẽ chuyển sang true
			dfs(thanh, thanh, 1, vc, -1, -1);
			while (flag) { // phá liên tục cho đến khi không còn cạnh để phá nữa
				reset();
				visit[thanh] = 1;
				flag = false;
				dfs(thanh, thanh, 1, vc, -1, -1);
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other_2\\TanCongThanhTri_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt();
			A = new int[n][n];
			mayBD = new int[n];
			for (int i = 0; i < n; i++) {
				int thanh = sc.nextInt();
				int soMayBD = sc.nextInt();
				int slKe = sc.nextInt();
				mayBD[thanh] = soMayBD;
				for (int j = 0; j < slKe; j++) {
					int tempThanh = sc.nextInt();
					A[thanh][tempThanh] = 1;
					A[tempThanh][thanh] = 1;
				}
			}
			ans = 0;
			visit = new int[n];
			solve();
			System.out.println("Case #" + tc + ": " + ans);
		}
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class TheFrog {
	static final int LOW_ENERGY = 1;
	static final int HIGH_ENERGY = 200;
	static final int INF = 1000000000;

	static int N;
	static int[] x, y, r; // tọa độ và bán kính của lá
	static int[] minEnergy; // lưu năng lượng nhỏ nhất để nhảy tới một chiếc lá bất kỳ
	static int[][] energy;
	static boolean[] visit;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\TheFrog_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			x = new int[N];
			y = new int[N];
			r = new int[N];
			minEnergy = new int[N];
			energy = new int[N][N];
			visit = new boolean[N];
			for (int i = 0; i < N; i++) {
				x[i] = sc.nextInt();
				y[i] = sc.nextInt();
				r[i] = sc.nextInt();
				minEnergy[i] = INF; // theo nguyên tắc dijkstra
				for (int j = 0; j < i; j++) { // tat ca cac cap (i, j)
					energy[i][j] = energy[j][i] = cal(i, j);
				}
			}
			Dijkstra();
			if (minEnergy[N - 1] == INF) {
				System.out.println(-1);
			} else {
				System.out.println((minEnergy[N - 1] / HIGH_ENERGY) + " " + (minEnergy[N - 1] % HIGH_ENERGY));
			}
		}
	}

	public static int cal(int i, int j) {
		// tinh duong cheo
		int dis = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
		int nearDis = (r[i] + r[j] + 40) * (r[i] + r[j] + 40);
		int farDis = (r[i] + r[j] + 90) * (r[i] + r[j] + 90);

		if (dis <= nearDis) {
			return LOW_ENERGY;
		} else if (dis <= farDis) {
			return HIGH_ENERGY;
		} else {
			return INF;
		}
	}

	public static void Dijkstra() {
		// khởi tạo
		minEnergy[0] = 0;
		int count = 0;
		int curLeaf = 0;

		while (count < N) {
			// tìm chiếc lá gần nhất, vòng đầu là 0
			int minE = INF;
			for (int i = 0; i < N; i++) {
				if (!visit[i] && minEnergy[i] < minE) {
					minE = minEnergy[i];
					curLeaf = i;
				}
			}
			// không cần
//			if (minE == INF || curLeaf == N - 1) { 
//				return;
//			}
			visit[curLeaf] = true; // đánh dấu và cập nhật trọng số tới các đỉnh
			for (int i = 0; i < N; i++) {
				if (!visit[i] && minEnergy[curLeaf] + energy[curLeaf][i] < minEnergy[i]) {
					minEnergy[i] = minEnergy[curLeaf] + energy[curLeaf][i];
				}
			}
			count++;
		}
	}
}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

public class ValidParenthese {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\ValidParenthese_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		int tc = 1;
		while (T-- > 0) {
			int N = sc.nextInt();
			String str = sc.next();
			System.out.println("#" + tc + " " + isValid(str));
			tc++;
		}
	}

	public static int isValid(String s) {
		Stack<Character> stack = new Stack<>();
		for (char c : s.toCharArray()) {
			if (c == '(' || c == '[' || c == '{' || c == '<') {
				stack.push(c);
			} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
				stack.pop();
			} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
				stack.pop();
			} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
				stack.pop();
			} else if (c == '>' && !stack.isEmpty() && stack.peek() == '<') {
				stack.pop();
			} else {
				return 0;
			}
		}
		if (stack.isEmpty()) {
			return 1;
		} else
			return 0;
	}

}

package Other;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class WellProject {
	static int N;
	static int[][] map;
	static int[] key;
	static int[] parent;
	static boolean[] visited;
	static int result;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\Other\\WellProject_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			map = new int[N][N];

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			visited = new boolean[N + 1];
			key = new int[N + 1];
			parent = new int[N + 1];
			for (int i = 0; i < N; i++) {
				key[i] = Integer.MAX_VALUE;
				parent[i] = -1;
			}
			key[0] = 0;

			// Phan code giai quyet
			for (int i = 0; i < N - 1; i++) {
				int u = findMinKey(); // dau tien u se la dinh 0
				visited[u] = true;
				for (int v = 0; v < N; v++) {
					if (!visited[v] && map[u][v] < key[v]) {
						key[v] = map[u][v];
						parent[v] = u;
					}
				}
			}
			result = 0;
			for (int v = 1; v < N; v++) {
				result += map[v][parent[v]];
			}

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

	public static int findMinKey() {
		int Min = Integer.MAX_VALUE;
		int index = -1;
		for (int v = 0; v < N; v++) {
			if (!visited[v] && key[v] < Min) {
				Min = key[v];
				index = v;
			}
		}
		return index;
	}

}

// CODE QUEUE CHUAN
// Queue vòng với kiểu int
// front = 0; rear = -1
class CircleQueue {
	int[] queue;
	int front, rear;
	int size, capacity;

	Queue(int maxSize) {
        queue = new int[maxSize];
        front = 0;
        rear = -1;
        size = 0;
        capacity = maxSize;
    }

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void add(int item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear = (rear + 1) % capacity;
		queue[rear] = item;
		size++;
	}

	int poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}

		int item = queue[front];
		queue[front] = 0;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front = (front + 1) % capacity;
		}
		size--;
		return item;
	}

	int front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	int rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	int size() {
		return size;
	}

	boolean isEmpty() {
		return size == 0;
		// return rear = -1;
		// return front > rear;
	}

	boolean isFull() {
		return size == capacity;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		for (int i = 0; i < size; i++) {
			int index = (front + i) % capacity;
			System.out.print(queue[index] + " ");
		}
		System.out.println();

	}
}

// Queue vòng, kiểu Object
// front = 0; rear = -1
class CircleQueue {
	Object[] queue;
	int front, rear;
	int size, capacity;

	CircleQueue(int maxSize) {
		queue = new Object[maxSize];
		front = 0;
		rear = -1;
		size = 0;
		capacity = maxSize;
	}

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void add(Object item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear = (rear + 1) % capacity;
		queue[rear] = item;
		size++;
	}

	Object poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}

		Object item = queue[front];
		queue[front] = null;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front = (front + 1) % capacity;
		}
		size--;
		return item;
	}

	Object front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	Object rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	int size() {
		return size;
	}

	boolean isEmpty() {
		return size == 0;
	}

	boolean isFull() {
		return size == capacity;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		for (int i = 0; i < size; i++) {
			int index = (front + i) % capacity;
			System.out.print(queue[index] + " ");
		}
		System.out.println();
	}
}

// Queue vòng, kiểu 1D array int[]
class CircleQueue {
	int[][] queue;
	int front, rear;
	int size, capacity;

	CircleQueue(int maxSize) {
		queue = new int[maxSize][];
		front = 0;
		rear = -1;
		size = 0;
		capacity = maxSize;
	}

	void add(int[] item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}

		rear = (rear + 1) % capacity;
		queue[rear] = item;
		size++;
	}

	int[] poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		int[] item = queue[front];
		queue[front] = null;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front = (front + 1) % capacity;
		}
		size--;
		return item;
	}

	int[] front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	int[] rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	int size() {
		return size;
	}

	boolean isEmpty() {
		return size == 0;
	}

	boolean isFull() {
		return size == capacity;
	}

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
		} else {
			for (int i = front; i != rear; i = (i + 1) % capacity) {
				System.out.print("[");
				for (int j = 0; j < queue[i].length; j++) {
					System.out.print(queue[i][j]);
					if (j < queue[i].length - 1) {
						System.out.print(", ");
					}
				}
				System.out.print("] ");
			}
			System.out.println();
		}
	}
}

// kiểu int
class Queue {
	int[] queue;
	int front, rear;
	int size, capacity;

	public Queue(int maxSize) {
		queue = new int[maxSize];
		front = 0;
		rear = -1;
		size = 0;
		capacity = maxSize;
	}

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void add(int item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear++;
		queue[rear] = item;
		size++;
	}

	int poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		int item = queue[front];
		queue[front] = 0;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front++;
		}
		size--;
		return item;
	}

	int front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	int rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	boolean isEmpty() {
		return size == 0;
	}

	boolean isFull() {
		return size == capacity;
	}

	void print() {
		for (int i = front; i <= rear; i++) {
			System.out.print(queue[i] + " ");
		}
		System.out.println();
	}
}

// kiểu int[]
class Queue {
	int[][] queue;
	int front, rear;
	int size, capacity;

	public Queue(int maxSize) {
		queue = new int[maxSize][];
		front = 0;
		rear = -1;
		size = 0;
		capacity = maxSize;
	}

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void add(int[] item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear++;
		queue[rear] = item;
		size++;
	}

	int[] poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		int[] item = queue[front];
		queue[front] = null;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front++;
		}
		size--;
		return item;
	}

	int[] front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	int[] rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	boolean isEmpty() {
		return size == 0;
	}

	boolean isFull() {
		return size == capacity;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
		} else {
			for (int i = front; i <= rear; i++) {
				System.out.print("[");
				for (int j = 0; j < queue[i].length; j++) {
					System.out.print(queue[i][j]);
					if (j < queue[i].length - 1) {
						System.out.print(", ");
					}
				}
				System.out.print("] ");
			}
			System.out.println();
		}
	}

}

// kiểu String
class Queue {
	String[] queue;
	int front, rear;
	int size, capacity;

	public Queue(int maxSize) {
		queue = new String[maxSize];
		front = 0;
		rear = -1;
		size = 0;
		capacity = maxSize;
	}

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void add(String item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear++;
		queue[rear] = item;
		size++;
	}

	String poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		String item = queue[front];
		queue[front] = null;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front++;
		}
		size--;
		return item;
	}

	String front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	String rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	boolean isEmpty() {
		return size == 0;
	}

	boolean isFull() {
		return size == capacity;
	}

	void print() {
		for (int i = front; i <= rear; i++) {
			System.out.print(queue[i] + " ");
		}
		System.out.println();
	}
}

// kiểu Object
class Queue {
	Object[] queue;
	int front, rear;
	int size, capacity;

	public Queue(int maxSize) {
		queue = new Object[maxSize];
		front = 0;
		rear = -1;
		size = 0;
		capacity = maxSize;
	}

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void add(Object item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear++;
		queue[rear] = item;
		size++;
	}

	Object poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		Object item = queue[front];
		queue[front] = null;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front++;
		}
		size--;
		return item;
	}

	Object front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	Object rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	boolean isEmpty() {
		return size == 0;
	}

	boolean isFull() {
		return size == capacity;
	}

	void print() {
		for (int i = front; i <= rear; i++) {
			System.out.print(queue[i] + " ");
		}
		System.out.println();
	}
}

// kiểu Point
class Queue {
	Point[] queue;
	int front, rear;
	int size, capacity;

	public Queue(int maxSize) {
		queue = new Point[maxSize];
		front = 0;
		rear = -1;
		size = 0;
		capacity = maxSize;
	}

	void reset() {
		front = 0;
		rear = -1;
		size = 0;
	}

	void add(Point item) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear++;
		queue[rear] = item;
		size++;
	}

	void add2(int x, int y) {
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		rear++;
		queue[rear] = new Point(x, y);
		size++;
	}

	Point poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		Point item = queue[front];
		queue[front] = null;
		if (front == rear) {
			front = 0;
			rear = -1;
		} else {
			front++;
		}
		size--;
		return item;
	}

	Point front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[front];
	}

	Point rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return queue[rear];
	}

	boolean isEmpty() {
		return size == 0;
	}

	boolean isFull() {
		return size == capacity;
	}

	void print() {
		for (int i = front; i <= rear; i++) {
			System.out.print("(" + queue[i].x + ", " + queue[i].y + ") ");
		}
		System.out.println();
	}
}

class Stack {
	int[] stack;
	int top;
	int capacity;

	Stack(int maxSize) {
		stack = new int[maxSize];
		top = -1;
		capacity = maxSize;
	}

	void push(int val) {
		if (isFull()) {
			System.out.println("Stack is full");
			System.exit(1);
		}
		top++;
		stack[top] = val;
	}

	int pop() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		int val = stack[top];
		top--;
		return val;
	}

	int peek() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		return stack[top];
	}

	int bottom() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		return stack[0];
	}

	boolean isEmpty() {
		return top == -1;
	}

	boolean isFull() {
		return top == capacity - 1;
	}

	int size() {
		return top + 1;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		for (int i = 0; i <= top; i++) {
			System.out.print(stack[i] + " ");
		}
		System.out.println();

	}

}

// kiểu int[]
class Stack {
	int top;
	int[][] stack;
	int capacity;

	Stack(int maxSize) {
		stack = new int[maxSize][];
		top = -1;
		capacity = maxSize;
	}

	void push(int[] val) {
		if (isFull()) {
			System.out.println("Stack is full");
			System.exit(1);
		}
		top++;
		stack[top] = val;
	}

	int[] pop() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		int[] val = stack[top];
		top--;
		return val;
	}

	int[] peek() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		return stack[top];
	}

	int[] bottom() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		return stack[0];
	}

	boolean isEmpty() {
		return top == -1;
	}

	boolean isFull() {
		return top == capacity - 1;
	}

	int size() {
		return top + 1;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		for (int i = 0; i <= top; i++) {
			System.out.print("[");
			for (int j = 0; j < stack[i].length; j++) {
				System.out.print(stack[i][j]);
				if (j < stack[i].length - 1) {
					System.out.print(", ");
				}
			}
			System.out.print("] ");
		}
		System.out.println();
	}
}

// kiểu Object
class Stack {
	int top;
	Object[] stack;
	int capacity;

	Stack(int maxSize) {
		stack = new Object[maxSize];
		top = -1;
		capacity = maxSize;
	}

	void push(Object val) {
		if (isFull()) {
			System.out.println("Stack is full");
			System.exit(1);
		}
		top++;
		stack[top] = val;
	}

	Object pop() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		Object val = stack[top];
		top--;
		return val;
	}

	Object peek() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		return stack[top];
	}

	Object bottom() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		return stack[0];
	}

	boolean isEmpty() {
		return top == -1;
	}

	boolean isFull() {
		return top == capacity - 1;
	}

	int size() {
		return top + 1;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		for (int i = 0; i <= top; i++) {
			System.out.print(stack[i] + " ");
		}
		System.out.println();

	}
}

// KIỂU POINT
class Stack {
	int top;
	Point[] stack;
	int capacity;

	Stack(int maxSize) {
		stack = new Point[maxSize];
		top = -1;
		capacity = maxSize;
	}

	void push(Point val) {
		if (isFull()) {
			System.out.println("Stack is full");
			System.exit(1);
		}
		top++;
		stack[top] = val;
	}

	void push2(int x, int y) {
		if (isFull()) {
			System.out.println("Stack is full");
			System.exit(1);
		}
		top++;
		stack[top] = new Point(x, y);
	}

	Point pop() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		Point val = stack[top];
		top--;
		return val;
	}

	Point peek() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		return stack[top];
	}

	Point bottom() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
			System.exit(1);
		}
		return stack[0];
	}

	boolean isEmpty() {
		return top == -1;
	}

	boolean isFull() {
		return top == capacity - 1;
	}

	int size() {
		return top + 1;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Stack is empty");
		} else {
			for (int i = 0; i <= top; i++) {
				System.out.print("(" + stack[i].x + ", " + stack[i].y + ") ");
			}
			System.out.println();
		}
	}

}


public class StackQueue {

	public static void main(String[] args) {

	}

}

// nguyên lý xếp chồng, mỗi khi tăng thì giá trị của top cũng tăng trước để gán giá trị mới
class Stack {
	int[] arr;
	int t;
	int capacity;

	Stack(int max) {
		arr = new int[max];
		t = -1;
		capacity = max;
	}

	void reset() {
		t = -1;
	}

	void push(int val) {
		arr[++t] = val;
	}

	int pop() {
		return arr[t--];
	}

	int peek() {
		return arr[t];
	}

	int bottom() {
		return arr[0];
	}

	boolean isEmpty() {
		return t == -1;
	}

	boolean isFull() {
		return t == capacity - 1;
	}

	int size() {
		return t + 1;
	}
}

// nguyên lý vào trước-ra trước, vào sau-ra sau
// front = head = lấy phần tử ra ở đầu; rear = tail = thêm phần tử vào cuối
// khi thêm phần tử, rear sẽ tăng lên, tức là đuôi dài ra, trong khi đầu cố định
// xem hình ảnh minh họa để hiểu rõ
class Queue {
	int[] q;
	int f, r;
	int capacity;

	Queue(int max) {
		q = new int[max];
		f = 0;
		r = -1;
		capacity = max;
	}

	void reset() {
		f = 0;
		r = -1;
	}

	void add(int val) { // enqueue
		if (isFull()) {
			System.out.println("Queue is full");
			System.exit(1);
		}
		q[++r] = val;
	}

	int poll() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return q[f++];
	}

	int front() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return q[f];
	}

	int rear() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			System.exit(1);
		}
		return q[r];
	}

	boolean isEmpty() {
		return f > r;
	}

	boolean isFull() {
		return size() == capacity;
	}

	int size() {
		return r - f + 1;
	}

	void print() {
		if (isEmpty()) {
			System.out.println("Queue is empty");
			return;
		}
		for (int i = f; i <= r; i++) {
			System.out.print(q[i] + " ");
		}
		System.out.println();
	}
}

class Point {
	int x, y;

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}


// CODE APS1:
package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class CountPrimeNumbers {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream(
				"src\\APS1\\countprimenumber_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt();
			boolean[] danhdau = new boolean[N + 1];
			int count = 0;
			for (int i = 2; i <= Math.sqrt(N); i++) {
				int j = 2;
				while (i * j <= N) {
					danhdau[i * j] = true;
					j++;
				}
			}
			for (int i = 2; i <= N; i++) {
				if (!danhdau[i]) {
					count++;
				}
			}
			System.out.print("#" + tc + " " + count);
			System.out.println();
		}
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class FindingMode {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\FindingMode_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		while (T-- > 0) {
			int tc = sc.nextInt();
			int[] scores = new int[1000];
			for (int i = 0; i < 1000; i++) {
				scores[i] = sc.nextInt();
			}
			int max = Integer.MIN_VALUE;
			int res = Integer.MIN_VALUE;
			int[] countDuplicate = new int[1000];
			for (int i = 0; i < 1000; i++) {
				countDuplicate[scores[i]]++;
			}
			for (int i = 0; i < 1000; i++) {
				if (max < countDuplicate[i] || (max == countDuplicate[i] && res < i)) {
					max = countDuplicate[i];
					res = i;
				}
			}
			System.out.println("#" + tc + " " + res);
		}
	}
}

package APS1;

// cach 2 dung counting sort
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Flatten {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\Flatten_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		int tc = 1;
		while (T-- > 0) {
			int soLuot = sc.nextInt();
			int[] arr = new int[100];
			for (int i = 0; i < 100; i++) {
				arr[i] = sc.nextInt();
			}
			while (soLuot-- > 0) {
				int min = findMinMax(arr)[0];
				int max = findMinMax(arr)[1];
				int minIndex = -1;
				int maxIndex = -1;
				for (int i = 0; i < arr.length; i++) {
					if (arr[i] == min) {
						minIndex = i;
						break;
					}
				}
				for (int i = 0; i < arr.length; i++) {
					if (arr[i] == max) {
						maxIndex = i;
						break;
					}
				}
				arr[minIndex]++;
				arr[maxIndex]--;
			}
			int finalMin = findMinMax(arr)[0];
			int finalMax = findMinMax(arr)[1];
			int res = finalMax - finalMin;
			System.out.println("#" + tc + " " + res);
			tc++;
		}
	}

	public static int[] findMinMax(int[] arr) {
		int min = arr[0];
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (min > arr[i]) {
				min = arr[i];
			}
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		return new int[] { min, max };
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Flatten_Cach2 {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\Flatten_input.txt"));
		Scanner sc = new Scanner(System.in);
		for (int test_case = 1; test_case <= 10; test_case++) {
			int dump = sc.nextInt();
			int[] arr = new int[100];
			for (int i = 0; i < 100; i++) {
				arr[i] = sc.nextInt();
			}
			Arrays.sort(arr);
			for (int i = 0; i < dump; i++) {
				arr[0]++;
				arr[99]--;
				Arrays.sort(arr);
			}
			System.out.println("#" + test_case + " " + (arr[99] - arr[0]));
		}
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Flatten_CountingSort {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\Flatten_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		int tc = 1;
		while (T-- > 0) {
			int soLuot = sc.nextInt();
			int[] arr = new int[100];
			int[] count = new int[101];
			int min = Integer.MAX_VALUE;
			int max = Integer.MIN_VALUE;
			for (int i = 0; i < 100; i++) {
				arr[i] = sc.nextInt();
				count[arr[i]]++;
				min = Math.min(arr[i], min);
				max = Math.max(arr[i], max);
			}
			// System.out.println(min + " " + max);
			int res = 0;
			for (int i = 0; i < soLuot; i++) {
				if (min < max) {
					count[max]--;
					count[min]--;
					count[max - 1]++;
					count[min + 1]++;
					if (count[min] == 0) {
						min = min + 1;
					}
					if (count[max] == 0) {
						max = max - 1;
					}
				} else if (min == max) {
					min++;
					max--;
				} else {
					min--;
					max++;
				}
			}
			res = Math.abs(min - max);
			System.out.println("#" + tc + " " + res);
			tc++;
		}
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class GeneratePassword {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\GeneratePassword_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		while (T-- > 0) {
			int tc = sc.nextInt();
			int[] arr = new int[8];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = sc.nextInt();
			}
			int demTang = 1;
			while (true) {
				if (demTang > 5) {
					demTang = 1;
				}
				if (arr[0] - demTang > 0) {
					int temp = arr[0] - demTang;
					for (int j = 0; j <= arr.length - 2; j++) {
						arr[j] = arr[j + 1];
					}
					arr[arr.length - 1] = temp;
					demTang++;
				} else {
					for (int j = 0; j <= arr.length - 2; j++) {
						arr[j] = arr[j + 1];
					}
					arr[arr.length - 1] = 0;
					break;
				}
			}
			System.out.print("#" + tc + " ");
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
		}
	}
}

package APS1;

// cach 3 nhay cot
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Ladder1_Cach1 {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\Ladder1_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		while (T-- > 0) {
			int tc = sc.nextInt();
			int[][] arr = new int[100][100];
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr[0].length; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			int res = -1;
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr[0].length; j++) {
					if (arr[i][j] == 2) {
						// System.out.println(j);
						int curRow = i;
						int curCol = j;
						while (true) {
							if (curRow == 0) {
								break;
							}
							if (curCol - 1 >= 0 && arr[curRow][curCol - 1] == 1) {
								curCol = curCol - 1;
								arr[curRow][curCol] = 3;
							} else if (curCol + 1 <= 99 && arr[curRow][curCol + 1] == 1) {
								curCol = curCol + 1;
								arr[curRow][curCol] = 3;
							} else {
								curRow = curRow - 1;
								arr[curRow][curCol] = 3;
							}
							// System.out.print(curCol + " ");
						}
						res = curCol;
					}
				}
			}
			System.out.println("#" + tc + " " + res);
		}
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Ladder1_Cach4 {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\Ladder1_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		while (T-- > 0) {
			int tc = sc.nextInt();
			int[][] ladder = new int[100][100];
			for (int i = 0; i < 100; i++) {
				for (int j = 0; j < 100; j++) {
					ladder[i][j] = sc.nextInt();
				}
			}
			int B = -1;
			for (int i = 0; i < 100; i++) {
				if (ladder[99][i] == 2) {
					B = i;
					// System.out.println(B);
					break;
				}
			}
			for (int i = 99; i >= 0; i--) {
				if (B > 0 && ladder[i][B - 1] == 1) {
					while (B > 0 && ladder[i][B - 1] == 1) {
						B--;
					}
					// System.out.println("Luot1 " + i);
				} else if (B < 99 && ladder[i][B + 1] == 1) {
					while (B < 99 && ladder[i][B + 1] == 1) {
						B++;
					}
					// System.out.println("Luot2 " + i);
				}
				// System.out.print(B + " ");
			}
			System.out.println("#" + tc + " " + B);
		}
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class LadderGame_Cach2 {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\LadderGame_input.txt"));
		Scanner sc = new Scanner(System.in);
		for (int t = 1; t <= 10; t++) {
			int N = sc.nextInt();
			int B = sc.nextInt();
			int M = sc.nextInt();
			int[][] ladder = new int[N + 1][N + 1];
			for (int i = 0; i < M; i++) {
				int x1 = sc.nextInt();
				int y1 = sc.nextInt();
				int x2 = sc.nextInt();
				int y2 = sc.nextInt();
				ladder[x1][y1] = y2;
				ladder[x2][y2] = y1;
			}
			for (int i = N - 1; i >= 1; i--) {
				if (ladder[i][B] != 0) {
					B = ladder[i][B];
				}
			}
			System.out.println("#" + t + " " + B);
		}
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class LadderGame_Cach3 {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\LadderGame_input.txt"));
		Scanner sc = new Scanner(System.in);
		for (int t = 1; t <= 10; t++) {
			int N = sc.nextInt();
			int B = sc.nextInt();
			int M = sc.nextInt();
			int[][] ladder = new int[2 * M][2];
			for (int i = 0; i < M; i++) {
				ladder[2 * i][0] = sc.nextInt();
				ladder[2 * i][1] = sc.nextInt();
				ladder[2 * i + 1][0] = sc.nextInt();
				ladder[2 * i + 1][1] = sc.nextInt();
			}
			for (int i = N - 1; i >= 1; i--) {
				for (int j = 0; j < 2 * M; j++) {
					if (ladder[j][0] == i && ladder[j][1] == B) {
						B = ladder[(j % 2 == 0) ? j + 1 : j - 1][1];
						break;
					}
				}
			}
			System.out.println("#" + t + " " + B);
		}
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class LadderGame_Cach4 {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\LadderGame_input.txt"));
		Scanner sc = new Scanner(System.in);
		for (int t = 1; t <= 10; t++) {
			int N = sc.nextInt();
			int B = sc.nextInt();
			int M = sc.nextInt();
			int[][] ladder = new int[N + 1][N + 1];
			for (int i = 0; i < M; i++) {
				int x1 = sc.nextInt();
				int y1 = sc.nextInt();
				int x2 = sc.nextInt();
				int y2 = sc.nextInt();
				ladder[x1][y1] = i + 1;
				ladder[x2][y2] = i + 1;
			}
			for (int i = N - 1; i >= 1; i--) {
				if (ladder[i][B] != 0) {
					for (int j = 1; j <= N; j++) {
						if (ladder[i][j] == ladder[i][B] && j != B) {
							B = j;
							break;
						}
					}
				}
			}
			System.out.println("#" + t + " " + B);
		}
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Palindrome1 {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\Palindrome1_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		int tc = 1;
		while (T-- > 0) {
			System.out.print("#" + tc + " ");
			tc++;
			int n = sc.nextInt();
			char[][] arr = new char[8][8];
			for (int i = 0; i < arr.length; i++) {
				String line = sc.next();
				for (int j = 0; j < arr[0].length; j++) {
					arr[i][j] = line.charAt(j);
				}
			}
			System.out.print(countPalindromes(arr, n));
			System.out.println();
		}
	}

	public static int countPalindromes(char[][] matrix, int N) {
		int rows = matrix.length;
		int cols = matrix[0].length;
		int count = 0;
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j <= cols - N; j++) {
				String rowString = "";
				for (int k = j; k < j + N; k++) {
					rowString += matrix[i][k];
				}
				if (isPalindrome(rowString)) {
					count++;
					// System.out.println(rowString);
				}
			}
		}
		for (int i = 0; i < cols; i++) {
			for (int j = 0; j <= rows - N; j++) {
				String colString = "";
				for (int k = j; k < j + N; k++) {
					colString += matrix[k][i];
				}
				if (isPalindrome(colString)) {
					count++;
					// System.out.println(colString);
				}
			}
		}
		return count;
	}

	public static boolean isPalindrome(String str) {
		int n = str.length();
		for (int i = 0; i < n / 2; i++) {
			if (str.charAt(i) != str.charAt(n - i - 1)) {
				return false;
			}
		}
		return true;
	}
}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class StockExchange {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\StockExchange_input.txt"));
//      System.setIn(new FileInputStream("src\\APS1\\StockExchange_input2.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt();
			int[] arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
			}
			System.out.println("#" + tc + " " + maxProfit(arr));
		}

	}

	public static int maxProfit(int prices[]) {
		int maxProfit = 0;
		int maxPriceIndex = findMaxPriceIndex(prices);
		for (int i = 0; i < maxPriceIndex; i++) {
			maxProfit += prices[maxPriceIndex] - prices[i];
		}
		if (maxPriceIndex <= prices.length - 2) {
			int[] remainingPrices = new int[prices.length - maxPriceIndex - 1];
			System.arraycopy(prices, maxPriceIndex + 1, remainingPrices, 0, remainingPrices.length);
			maxProfit += maxProfit(remainingPrices);
		}
		return maxProfit;
	}

	public static int findMaxPriceIndex(int[] prices) {
		int maxPrice = prices[0];
		int maxPriceIndex = 0;
		for (int i = 0; i < prices.length; i++) {
			if (prices[i] > maxPrice) {
				maxPrice = prices[i];
				maxPriceIndex = i;
			}
		}
		return maxPriceIndex;
	}
}


package APS1;

// duyet 2 vong for, cho tung toa nha va sau do, voi moi toa nha duyet tu tang duoi cung
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class View_Cach1 {

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\View_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		int tc = 1;
		while (T-- > 0) {
			int n = sc.nextInt();
			int[] arr = new int[n];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = sc.nextInt();
			}
			int count = 0;
			for (int i = 2; i <= n - 3; i++) {
				for (int j = 1; j <= arr[i]; j++) {
					if (arr[i - 2] < j && arr[i - 1] < j && arr[i + 1] < j && arr[i + 2] < j) {
						count++;
					}
				}
			}
			System.out.println("#" + tc + " " + count);
			tc++;
		}
	}

}

package APS1;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class View_Cach2 {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS1\\View_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = 10;
		int tc = 1;
		while (T-- > 0) {
			int N = sc.nextInt();
			int[] buildings = new int[N];
			for (int i = 0; i < N; i++) {
				buildings[i] = sc.nextInt();
			}
			int answer = 0;
			for (int i = 2; i < N - 2; i++) {
				if (buildings[i] > buildings[i - 1] && buildings[i] > buildings[i - 2]
						&& buildings[i] > buildings[i + 1] && buildings[i] > buildings[i + 2]) {
					int max1 = Math.max(Math.max(buildings[i - 1], buildings[i - 2]),
							Math.max(buildings[i + 1], buildings[i + 2]));
					answer += buildings[i] - max1;
				}
			}
			System.out.println("#" + tc + " " + answer);
			tc++;
		}
	}
}

// SORT SEARCH
package SortSearch;

import java.util.Arrays;

public class Selection_Bubble {
	// https://www.programiz.com/java-programming/examples/bubble-sort
	// https://www.geeksforgeeks.org/bubble-sort/
	// https://www.javatpoint.com/bubble-sort-in-java

	// đây là phiên bản tối ưu của thuật toán buble sort
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] unsortedArr = { 52, 45, 32, 64, 12, 87, 78, 98, 23, 7 };
		bubbleSort(unsortedArr);
		System.out.println(Arrays.toString(unsortedArr));

		System.out.println();

		int[] unsortedArr2 = { 52, 45, 32, 64, 12, 87, 78, 98, 23, 7 };
		ChimDaySort(unsortedArr2);
		System.out.println(Arrays.toString(unsortedArr2));

	}

// thuật toán nổi bọt có mục đích: so sánh 2 số kề nhau, số lớn hơn cho index cao hơn, 
// cứ như vậy sẽ tìm ra số lớn nhất ở vị trí index cuối
// áp dụng như vậy trong n-1 vòng. Sau mỗi vòng, sẽ tìm được 1 số lớn nhất ở index trên cùng
// nên xét j < n-i-1 --> lỡ để j < n-1 thuật toán vẫn đúng
	static void bubbleSort(int[] arr) {
		boolean swapped;
		int n = arr.length;
		for (int i = 0; i < n - 1; i++) { // n-1 vòng sắp xếp
			swapped = false;
			for (int j = 0; j < n - i - 1; j++) {
// sau mỗi vòng sẽ có một số lớn nhất nổi lên trên nên điểm cuối là n-i-1
				if (arr[j] > arr[j + 1]) {
					// swap arr[j+1] and arr[j]
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					swapped = true;
				}
			}
			System.out.println(Arrays.toString(arr));
// IF no two elements were swapped by inner loop, then break
			if (swapped == false)
				break;
		}
	}

// thuật toán chìm đáy có mục đích: ban đầu lấy gốc arr[0], so sánh với các số sau, 
// cứ số nhỏ hơn thì gán vào arr[0] --> đến cuối cùng arr[0] sẽ là phần tử nhỏ nhất của mảng
// sau đó, áp dụng quy luật tương tự kể từ arr[1] trở đi...
	static void ChimDaySort(int[] arr) {
		int temp = 0;
		boolean swapped;
		// ascending order
		for (int i = 0; i < arr.length - 1; i++) { // n-1 vòng sắp xếp
			swapped = false;
			for (int j = i + 1; j < arr.length; j++) {
// sau mỗi vòng sẽ có 1 số nhỏ nhất chìm xuống đáy nên điểm xuất phát là i+1
				if (arr[i] > arr[j]) {
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
					swapped = true;
				}
			}
			System.out.println(Arrays.toString(arr));
			if (swapped == false)
				break;
		}
	}
}



package SortSearch;

public class MergeSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 19, 8, 1998, 30, 28, 6, 9 };
		mergeSort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}

	}

	public static void mergeSort(int[] array) {
		if (array.length > 1) {
			int mid = array.length / 2;
			int[] left = new int[mid];
			int[] right = new int[array.length - mid];
			System.arraycopy(array, 0, left, 0, mid);
			System.arraycopy(array, mid, right, 0, array.length - mid);

			mergeSort(left);
			mergeSort(right);
			merge(array, left, right);
		}
	}

	public static void merge(int[] result, int[] left, int[] right) {
		int i = 0;
		int j = 0;
		for (int k = 0; k < result.length; k++) {
			if (j >= right.length || (i < left.length && left[i] <= right[j])) {
				result[k] = left[i];
				i++;
			} else {
				result[k] = right[j];
				j++;
			}
		}
	}
}


package SortSearch;

public class QuickSort {

	// Hàm nhận phần tử cuối cùng làm chốt,
	// đặt các phần tử nhỏ hơn chốt ở trước
	// và lớn hơn ở sau nó
	int partition(int arr[], int low, int high) {
		int pivot = arr[high];
		int i = (low - 1); // index of smaller element
		for (int j = low; j < high; j++) {

			// Nếu phần tử hiện tại nhỏ hơn chốt
			if (arr[j] < pivot) {
				i++;

				// swap arr[i] và arr[j]
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}

		// swap arr[i+1] và arr[high] (hoặc pivot)
		int temp = arr[i + 1];
		arr[i + 1] = arr[high];
		arr[high] = temp;

		return i + 1;
	}

	// arr[] --> Mảng cần được sắp xếp,
	// low --> chỉ mục bắt đầu,
	// high --> chỉ mục kết thúc
	void sort(int arr[], int low, int high) {
		if (low < high) {

			// pi là chỉ mục của chốt, arr[pi] vị trí của chốt
			int pi = partition(arr, low, high);

			// Sắp xếp đệ quy các phần tử
			// trướcphân vùng và sau phân vùng
			sort(arr, low, pi - 1);
			sort(arr, pi + 1, high);
		}
	}

	// In các phần tử của mảng
	static void printArray(int arr[]) {
		int n = arr.length;
		for (int i = 0; i < n; ++i)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

	public static void main(String args[]) {
		int arr[] = { 10, 80, 30, 90, 40, 50, 70 };
		int n = arr.length;

		System.out.println("Mảng ban đầu:");
		printArray(arr);

		QuickSort ob = new QuickSort();
		ob.sort(arr, 0, n - 1);

		System.out.println("Mảng sau khi sắp xếp:");
		printArray(arr);
	}
}


package SortSearch;

import java.util.Arrays;

public class Sort2D {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// matrix[7][4]
		int[][] BXH = { { 5, 45, 85, 150 }, { 6, 48, 100, 200 }, { 4, 40, 80, 100 }, { 7, 50, 100, 200 },
				{ 6, 49, 100, 200 }, { 4, 40, 80, 120 }, { 5, 45, 90, 150 } };
		int[][] BXH2 = { { 5, 40, 80, 120 }, { 6, 40, 80, 120 }, { 4, 40, 80, 120 }, { 7, 40, 80, 120 },
				{ 6, 40, 80, 120 }, { 4, 40, 80, 120 }, { 5, 40, 80, 120 } };

		Arrays.sort(BXH, (a, b) -> {
			if (a[0] != b[0])
				return b[0] - a[0];
			else if (a[1] != b[1])
				return b[1] - a[1];
			else if (a[2] != b[2])
				return b[2] - a[2];
			else
				return b[3] - a[3];
		});
		Arrays.sort(BXH2, (a, b) -> {
			if (a[1] != b[1])
				return b[1] - a[1];
			else if (a[2] != b[2])
				return b[2] - a[2];
			else
				return b[3] - a[3];
		});
		for (int i = 0; i < BXH.length; i++) {
			System.out.print("#" + (i + 1) + ":" + " ");
			for (int j = 0; j < BXH[0].length; j++) {
				System.out.print(BXH[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
		for (int i = 0; i < BXH2.length; i++) {
			System.out.print("#" + (i + 1) + ":" + " ");
			for (int j = 0; j < BXH2[0].length; j++) {
				System.out.print(BXH2[i][j] + " ");
			}
			System.out.println();
		}

// Sort sử dụng swap 1
		int[][] Arr = { { 5, 45, 85, 150 }, { 6, 48, 100, 200 }, { 4, 40, 80, 100 }, { 7, 50, 100, 200 },
				{ 6, 49, 100, 200 }, { 4, 40, 80, 120 }, { 5, 45, 90, 150 } };
		for (int i = 0; i < Arr.length - 1; i++) {
			for (int j = i + 1; j < Arr.length; j++) {
				if (Arr[i][0] < Arr[j][0]) {
					swap(Arr, i, j);
				} else if (Arr[i][0] == Arr[j][0]) {
					if (Arr[i][1] < Arr[j][1]) {
						swap(Arr, i, j);
					} else if (Arr[i][1] == Arr[j][1]) {
						if (Arr[i][2] < Arr[j][2]) {
							swap(Arr, i, j);
						} else if (Arr[i][2] == Arr[j][2]) {
							if (Arr[i][3] < Arr[j][3]) {
								swap(Arr, i, j);
							}
						}
					}
				}
			}
		}
		System.out.println();
		for (int i = 0; i < Arr.length; i++) {
			System.out.print("#" + (i + 1) + ":" + " ");
			for (int j = 0; j < Arr[0].length; j++) {
				System.out.print(Arr[i][j] + " ");
			}
			System.out.println();
		}

		// Sort su dung swap 2
		int[][] Array = { { 5, 45, 85, 150 }, { 6, 48, 100, 200 }, { 4, 40, 80, 100 }, { 7, 50, 100, 200 },
				{ 6, 49, 100, 200 }, { 4, 40, 80, 120 }, { 5, 45, 90, 150 } };

		for (int i = 0; i < Array.length - 1; i++) {
			for (int j = i + 1; j < Array.length; j++) {
				if (Array[i][0] < Array[j][0]) {
					int[] temp = Array[i];
					Array[i] = Array[j];
					Array[j] = temp;
				} else if (Array[i][0] == Array[j][0]) {
					if (Array[i][1] < Array[j][1]) {
						int[] temp = Array[i];
						Array[i] = BXH[j];
						Array[j] = temp;
					} else if (Array[i][1] == Array[j][1]) {
						if (Array[i][2] < Array[j][2]) {
							int[] temp = BXH[i];
							Array[i] = Array[j];
							Array[j] = temp;
						} else if (Array[i][2] == Array[j][2]) {
							if (Array[i][3] < Array[j][3]) {
								int[] temp = Array[i];
								Array[i] = Array[j];
								Array[j] = temp;
							}
						}
					}
				}
			}
		}
		System.out.println();
		for (int i = 0; i < Array.length; i++) {
			System.out.print("#" + (i + 1) + ":" + " ");
			for (int j = 0; j < Array[0].length; j++) {
				System.out.print(Array[i][j] + " ");
			}
			System.out.println();
		}

// có thể dùng Arrays.sort() để đảo mảng, khi đó return 0 và return 1 sẽ giữ nguyên mảng ban đầu
		int[][] MangGoc = { { 5, 45, 85, 150 }, { 6, 48, 100, 200 }, { 4, 40, 80, 100 }, { 7, 50, 100, 200 },
				{ 6, 49, 100, 200 }, { 4, 40, 80, 120 }, { 5, 45, 90, 150 } };
		Arrays.sort(MangGoc, (a, b) -> 1);
// C2
		Arrays.sort(MangGoc, (a, b) -> {
			return 1;
		});
		// đảo mảng
//		Arrays.sort(MangGoc, (a, b) -> -1);

// C2 đảo mảng
		for (int i = 0; i < MangGoc.length / 2; i++) {
			int[] temp = MangGoc[i];
			MangGoc[i] = MangGoc[MangGoc.length - 1 - i];
			MangGoc[MangGoc.length - 1 - i] = temp;
		}

//		Arrays.sort(MangGoc, (a, b) -> a[0] - b[0]); // sort tăng dần cho a[0]
//		Arrays.sort(MangGoc, (a, b) -> b[1] - a[1]); // sort giảm dần cho a[1]
		System.out.println();
		for (int i = 0; i < MangGoc.length; i++) {
			System.out.print("#" + (i + 1) + ":" + " ");
			for (int j = 0; j < MangGoc[0].length; j++) {
				System.out.print(MangGoc[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void swap(int[][] arr, int i, int j) {
		int[] temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

package SortSearch;

import java.util.Arrays;

public class ArrayMinMax {
	public static void main(String[] args) {
		int[] arr = { 3, 5, 1, 9, 7 };
		int min = arr[0];
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] < min) {
				min = arr[i];
			}
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		// C2
		int[] sortedArr = arr.clone();
		Arrays.sort(sortedArr);
		int Min = sortedArr[0];
		int Max = sortedArr[4];
		System.out.println("Minimum value: " + min);
		System.out.println("Maximum value: " + max);
		System.out.println("Minimum value: " + Min);
		System.out.println("Maximum value: " + Max);

	}
}