full_solution

 avatar
SSkyFire
java
2 months ago
101 kB
0
Indexable
Never
1/////////////////////////////////////
point balance
package Point_of_balance_2;

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

// F = G*m1*m2/(d*d) ;
// n vat lieu tu tinh ton tai n-1 diem can bang

public class Solution_Point_of_Balance {
	
	static double MIN_DISTANCE = 0.000000001 ;
	static int[] pos ;
	static double[] weight ;
	static int N ;
	static double start, end, diemCanBang, curPos ; 
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/Point_of_balance_2/input_point_of_balance.txt"));
		Scanner sc = new Scanner(System.in);

		for (int tc = 1 ; tc <= 10; tc++) {
			N = sc.nextInt() ; //so luong vat lieu tu tinh
			//toa do
			pos = new int[N] ;
			for (int i = 0; i < N; i++) {
				pos[i] = sc.nextInt() ;
			}
			weight = new double[N] ;
			for (int i = 0; i < N; i++) {
				weight[i] = sc.nextInt() ;
			}
			System.out.print("#" + tc + " ");
			
			for (int i = 0; i < N - 1; i++) {
				//co n-1 diem can bang
				start = pos[i] ;
				end = pos[i+1] ;
				//curPos = (start + end) / 2 ;
				timDiemCanBang(start, end) ;
				System.out.printf( "%,.10f" , curPos);
				System.out.print(" ");
			}
			System.out.println();
		}
	}



	private static void timDiemCanBang(double left, double right) {
		double F_left = 0, F_right = 0, d, m;
		curPos = ( left + right) / 2 ;
		for (int i = 0; i < N ; i++) {
			d = abs(curPos - pos[i]) ;
			m = weight[i] ;
			if( pos[i] < curPos){
				F_left += m / (d*d) ;
			} else {
				F_right += m / (d*d) ;
			}
		}
		if( abs(F_left - F_right) < MIN_DISTANCE ){
			//sai so toa do nho hon 10^-9
			return ;
		}
		if( F_left > F_right){
			timDiemCanBang(curPos, right);
		} else if(F_left < F_right){
			timDiemCanBang(left, curPos);
		}
	}



	static double abs(double d){ // lay tri tuyet doi 
		if( d > 0) return d ;
		else return -d ;
	}
}

2//////////////////////////////////////////
minimal big sum
package minimal_big_sum;

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

public class Solution_mini_big_sum{
	static int  K, N ;
	static int map[] ;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/minimal_big_sum/input_minimal_b_s"));
		
		Scanner sc = new Scanner(System.in) ;
		int T = sc.nextInt() ;
		for (int tc = 1; tc <= T; tc++) {
			K = sc.nextInt() ; // so block
			N = sc.nextInt() ; // do dai phan tu trong mang
			
			map = new int[N+1] ;
			for (int i = 0; i < N; i++) {
				map[i] = sc.nextInt();
			}
			
			int tongCuaDay = 0;
			int phanTuMax = -1 ;
			for (int i = 0; i < N; i++) {
				tongCuaDay = tongCuaDay + map[i] ;
				phanTuMax = Math.max(phanTuMax, map[i]) ;
			}
			int left = phanTuMax ;
			int right = tongCuaDay ;
			System.out.println(tongCuaDay + " " + phanTuMax);
			int ans = timTongNhoNhat(left, right);
			System.out.println("#" + tc + " " + ans);
			 //timTongNhoNhat() ;
		}
	}
	private static int timTongNhoNhat(int left, int right) {
		
		while( left <= right){
			int mid = ( left + right) / 2;
			int soBlock = calcBlock(mid) ;
			if ( soBlock <= K){
				right = mid - 1 ;
			}
			else {
				left = mid + 1;
			}
		}
		return left ;
	}
	
	private static int calcBlock( int gioiHan) {
		int soBlock = 1;
		int sum = 0 ;
		for (int i = 0; i < map.length ; i++) {
			sum = sum + map[i] ;
			if( sum > gioiHan){
				soBlock++ ;
				sum = map[i] ;
			}
		}
		return soBlock;
	}
}

3////////////////////////////////////////////////
moutain walking

package moutain_walking;

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

public class Solution_moutain_walking {

	static class Queue {
		static int maxq = 100001;
		int data[] = new int[maxq];
		int front, rear;

		Queue() {
			front = rear = -1;
		}

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

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

		void enQueue(int v) {
			data[++rear] = v;
		}

		int deQueue() {
			return data[++front];
		}

		int peek() {
			return data[front + 1];
		}
	}

	static Queue qx = new Queue();
	static Queue qy = new Queue();
	static int N, sx, sy, ex, ey;
	static int left, right, mid;
	static int max_cur, min_cur ;
	static int map[][], visit[][];
	static int dx[] = { 0, -1, 0, 1 };
	static int dy[] = { -1, 0, 1, 0 };

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream(
				"last_hope/moutain_walking/input_moutain_walking.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 + 1][N + 1];
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					map[i][j] = sc.nextInt();
				}
			}

			max_cur = -1 ;
			min_cur = 111;
			//sx = 0;
			//sy = 0;
			ex = N;
			ey = N;
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					max_cur = Math.max(max_cur, map[i][j]);
					min_cur = Math.min(min_cur, map[i][j]);
				}
			}
			
			visit = new int[N + 1][N + 1];
			left = 0;// chenh lech do cao nho nhat co the
			right = max_cur - min_cur; // chenh lech do cao lon nhat co the			
			//mid = (left + right) / 2;

			//BFS();
			int ans = chatNhiPhan( 0, right) ;
			System.out.println("#" + tc + " " + ans);
		}
	}

	private static boolean BFS(int canDuoi, int canTren) {
		qx.reset();
		qy.reset();
//		qx.enQueue(sx);
//		qy.enQueue(sy);
//		visit[sx][sy] = 1;
		qx.enQueue(1);
		qy.enQueue(1);
		visit[1][1] = 1;
		while (!qx.isqEmpty()) {
			int r = qx.deQueue();
			int c = qy.deQueue();

			for (int i = 0; i < 4; i++) {
				int newr = r + dx[i];
				int newc = c + dy[i];

				if (newr >= 1 && newr <= N && newc >= 1 && newc <= N
						&& visit[newr][newc] == 0) {
					if (map[newr][newc] >= canDuoi && map[newr][newc] <= canTren) {
						
						if( newr == N && newc == N) return true; 
						visit[newr][newc] = 1;
						qx.enQueue(newr);
						qy.enQueue(newc);
						
					}
				}
			}
		}
		return false ;
	}
	
//	static boolean check(int mid){
//		
//		return false ;
//	}
	
	static void init() {
//		qx.reset();
//		qy.reset();
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				visit[i][j] = 0;
			}
		}
//		qx.enQueue(1);
//		qy.enQueue(1);
//		visit[1][1] = 1;
	}
	
	static int chatNhiPhan(int left, int right){
		while( left < right){
			int mid = ( left + right) / 2 ;
			int check = 0;
			for (int i = min_cur; i <= max_cur - mid; i++) {
				init() ;
				if( (map[1][1] >=i && map[1][1] <= i+mid ) )
				{ 
					if(BFS(i, i+ mid) == true){
					check = 1;
					//right = mid - 1;
					right = mid ;
					break;
					}
				}
			}
			if(check == 0){
				left = mid + 1;
			}
		}
		
		
		return left ;
	}
	
}
4////////////////////////////////////////////
clean robot
package cleaning_robot;

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

class Queue {
	private static final int MAX_SIZE = 1000000;
	private int[] data = new int[MAX_SIZE];
	private int front, rear;

	public Queue() {
		front = rear = -1;
	}

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

	void enQueue(int value) {
		data[++rear] = value;
	}

	int deQueue() {
		return data[++front];
	}

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

public class Solution_rb_ver2 {

	static final int INF = 1000000000;
	static int N, M, startX, startY, min, countDirty; // count: dem so o ban
	static int[][] map; // luu input
	static int[][] pos; // vi tri cac o ban
	static int[][] visit;
	static int[] visited;// lan va dem kc
	static int[][] maTranKe;
	static long startFunc, endFunc;
	static Queue row = new Queue();
	static Queue col = new Queue();
	static boolean check = false, checkAll;

	static int[] r_spin = { 0, 0, -1, 1 };
	static int[] c_spin = { -1, 1, 0, 0 };

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

		int T = sc.nextInt();
		//startFunc = System.currentTimeMillis();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();

			map = new int[N][M];
			pos = new int[N * M + 1][2];
			visit = new int[N][M];
			countDirty = 1;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 3) {
						pos[0][0] = i;
						pos[0][1] = j;
					}

					if (map[i][j] == 1) {
						pos[countDirty][0] = i;
						pos[countDirty][1] = j;
						countDirty++;
					}
				}
			}

			min = INF;
			checkAll = true;
			visited = new int[countDirty];
			maTranKe = new int[countDirty][countDirty];

			taoMaTranKe();

			backtrack(1, 0, 0);
			System.out.println("Case #" + tc);
			if (checkAll) {
				System.out.println(min);
			} else {
				System.out.println(-1);
			}
		}
		sc.close();
		//endFunc = System.currentTimeMillis();
		//System.out.println(endFunc - startFunc + " ms");
	}

	private static void taoMaTranKe() {

		for (int i = 0; i < countDirty - 1; i++) {
			for (int j = i + 1; j < countDirty; j++) {
				maTranKe[i][j] = BFS(pos[i][0], pos[i][1], pos[j][0], pos[j][1]);

				if (maTranKe[i][j] == -1) {
					checkAll = false;
				}
				maTranKe[j][i] = maTranKe[i][j];
			}
		}
	}

	private static void backtrack(int k, int cnt, int curNode) {
		if (min <= cnt) {
			return;
		}

		if (k == countDirty ) {
			min = min < cnt ? min : cnt;
			return;
		}

		for (int i = 1; i < countDirty; i++) {
			if (visited[i] == 0) {
				if (maTranKe[curNode][i] != 0) {
					visited[i] = 1;
					backtrack(k + 1, cnt + maTranKe[curNode][i], i);
					visited[i] = 0;
				}
			}
		}
	}

	private static int BFS(int startRow, int startCol, int endRow, int endCol) {
		row.reset();
		col.reset();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visit[i][j] = 0;
			}
		}

		visit[startRow][startCol] = 1;
		row.enQueue(startRow);
		col.enQueue(startCol);

		while (!row.isEmpty()) {
			int r = row.deQueue();
			int c = col.deQueue();

			for (int i = 0; i < 4; i++) {
				int newR = r + r_spin[i];
				int newC = c + c_spin[i];

				if (newR >= 0 && newC >= 0 && newR < N && newC < M) {
					if (visit[newR][newC] == 0 && map[newR][newC] != 2) {
						visit[newR][newC] = visit[r][c] + 1;
						row.enQueue(newR);
						col.enQueue(newC);
					}

					if (newR == endRow && newC == endCol) {
						return visit[r][c];
					}
				}
			}

		}
		return -1;
	}
}

5/////////////////////////////////////////
hugo mat ong
package Hugo_chi_ong_nau;

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



public class Solution_hugo_chi_ong_nau {
	static class Queue {
		static int maxq = 1000001;
		int data[] = new int[maxq];
		int front, rear;

		Queue() {
			front = rear = -1;
		}

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

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

		void enQ(int v) {
			data[++rear] = v;
		}

		int deQ() {
			return data[++front];
		}
	}
	static int M, N, ans;
	static int map[][];
	static int visit[][];
	static int dxChan[] = { -1, 0, 1, 1, 1, 0 };
	static int dyChan[] = { 0, 1, 1, 0, -1, -1 };

	static int dxLe[] = { -1, -1, 0, 1, 0, -1 };
	static int dyLe[] = {0, 1, 1, 0, -1, -1};

	static int dxT[] = {0, -1, 0, 1} ;
	static int dyT[] = {-1, 0, 1, 0} ;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream(
				"src/Hugo_chi_ong_nau/input_hugo_tim_mat.txt"));
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			M = sc.nextInt(); // so cot
			N = sc.nextInt(); // so hang

			map = new int[N + 1][M + 1];
			visit = new int[N + 1][M + 1];

			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			
			ans = 0;
			//resetVisit();
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					visit[i][j] = 1;
					backTrack(i, j, map[i][j], 1);
					//xuLychuT(i, j);
					visit[i][j] = 0;
				}
			}

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

	static void resetVisit() {

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

	static void backTrack(int r, int c, int honey, int thung) {
		// dk dung
		if (thung >= 4) {
			ans = Math.max(ans, honey);
			return;
		}
		
		int dx[] = new int[6];
		int dy[] = new int[6];
		if (c % 2 == 0) { // neu cot chan
			dx = dxChan;
			dy = dyChan;
		} else { // neu cot le
			dx = dxLe;
			dy = dyLe;
		}
		
		for (int k = 0; k < 6; k++) {
			int newr = r + dx[k];
			int newc = c + dy[k];
			if (newr > 0 && newr <= N && newc > 0 && newc <= M) {
				
				if (visit[newr][newc] == 0) {
					visit[newr][newc] = 1;
					
					backTrack(newr, newc, honey + map[newr][newc], thung + 1);
					backTrack(r, c, honey + map[newr][newc], thung + 1);
					// tra ve
					visit[newr][newc] = 0;
				}
			}

		}
		
	}
	//xu ly 4 o hinh chu T
	static void xuLychuT(int r, int c){
		int sum = map[r][c];
		int min = Integer.MAX_VALUE;
		int count = 0;
		
		for (int k = 0; k < 4; k++) {
			int newr = r + dxT[k] ;
			int newc = c + dyT[k] ;
			if( newr >0 && newr <= N && newc >0 && newc <= M){
				
				if (min > map[newr][newc]) {
					min = map[newr][newc];
				}
				sum += map[newr][newc];
			} else {
				count++;
			}
		}
		
		if (count == 0) { 
			sum -= min;
			ans = Math.max(ans, sum);
		} 
		else if (count == 1) { // lech ra khoi bien 1 phan tu
			ans = Math.max(ans, sum);
		}
	
	}
}

6/////////////////////////
pizza location

import java.util.Scanner;

public class Solution
{
	static final int mx = 20;
	static int K, R;// so nha hang, ban kinh phan phoi
	static int M; // so vi tri nha hang
	static int[] NhaHangX = new int[mx];
	static int[] NhaHangY = new int[mx];
	static int N;
	static int[] visitNhaHang = new int[mx];
	static int[] VuiChoiX = new int[100];
	static int[] VuiChoiY = new int[100];
	static int[] soNguoi = new int[100];
	static int[] visitVuiChoi = new int[100];

	static int tongSoNguoi, ansMaxSoNguoi;
	static int[][] que = new int[101][101];

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


		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			resetAll();
			K = sc.nextInt();// so nha hang
			R = sc.nextInt();// ban kinh phan phoi

			M = sc.nextInt();// so vi tri nha hang
			for (int i = 0; i < M; i++) {
				NhaHangX[i] = sc.nextInt();
				NhaHangY[i] = sc.nextInt();
			}

			N = sc.nextInt(); // dia diem vui choi
			for (int i = 0; i < N; i++) {
				VuiChoiX[i] = sc.nextInt();
				VuiChoiY[i] = sc.nextInt();
				soNguoi[i] = sc.nextInt();//so nguoi tai dia diem vui choi
			}
			
			ansMaxSoNguoi = 0; 
		
			backtrack(0, 0, 0);
			
			System.out.println("#" + tc + " " + ansMaxSoNguoi);
		}
	}

	private static void backtrack(int x, int k, int curTong) {
		int banKinh = R * R ;
		//dieu kien dung
		if( k == K){
			ansMaxSoNguoi = Math.max(ansMaxSoNguoi, curTong) ;
			return ;
		}
		
		for (int i = x; i < M; i++) {
			tongSoNguoi = 0 ;
			if( visitNhaHang[i] == 0){
				visitNhaHang[i] = 1 ;
				int dem = 0 ;
				
				for (int j = 0; j < N ; j++) {
					if( binhPhuong(VuiChoiX[j] - NhaHangX[i]) 
							+ binhPhuong(VuiChoiY[j] - NhaHangY[i]) <= banKinh){
						if( visitVuiChoi[j] == 0){
							visitVuiChoi[j] = 1;
							tongSoNguoi += soNguoi[j] ;
							que[i][dem++] = j ; // dung de tra visit vui choi
						}
					}
				}
				backtrack(i, k + 1, curTong + tongSoNguoi);
				visitNhaHang[i] = 0;
				for (int j = 0; j < dem; j++) {
					visitVuiChoi[ que[i][j]] = 0;
				}
			}
		}
		
	}

	static int binhPhuong(int k) {
		return k * k;
	}

	private static void resetAll() {
		tongSoNguoi = 0;
		ansMaxSoNguoi = 0;
		for (int i = 0; i < M; i++) {
			visitNhaHang[i] = 0;
		}
		for (int i = 0; i < N; i++) {
			visitVuiChoi[i] = 0;
		}

	}
}
7////////////////////////////////////
hugo di tau
package hugo_di_tau;

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

public class Solution_hugo_di_tau {
	static int n, res;
	static int[] check, visit, p, c;

	static void solve1(int count, int sum) {
		//dem 0, 1, 2 --> den 3 thi dung va in ra khoang cach max
		if (count == 3) {//dieu kien dung
			if (sum < res) {
				res = sum;
			}
			return;
		}
		for (int i = 1; i <= 3; i++) {
			
			if(visit[i] == 0){
				visit[i] = 1; 
				int people = c[i] ;
				int value = sum ; // value luu tong khoang nguoi den ghe
				
				int j = 0;
				while( j<=10){//lan chinh vi tri do va sang phai
					if(p[i] + j <= n){
						if( check[p[i] + j] == 0 ){
							check[p[i] + j] = i ; // danh dau vi tri cho ngoi
							value = value + ( j + 1) ;//tang so nguoi tren vi tri ghe
							people-- ; // giam so nguoi cho
						}
						if(people == 0){
							break ;
						}
					}
					if(p[i] - j > 0){
						if(check[p[i] - j] == 0){
							check[p[i] - j] = i ;
							value = value + (j + 1) ;
							people-- ;
						}
						
					}
					if( people == 0)
					{
						break ; 
					}
				}
			}
		}
	}

	static void solve2(int count, int sum) {
		if (count == 3) {
			if (sum < res) {
				res = sum;
			}
			return;
		}
		for (int i = 1; i <= 3; i++) {
			if (visit[i] == 0) {
				visit[i] = 1;
				int people = c[i];
				int value = sum;
				int j = 0;
				while (j <= n) { // lan trai truoc
					if (p[i] - j > 0) {
						if (check[p[i] - j] == 0) {
							check[p[i] - j] = i;
							value += j + 1;
							people--;
						}
						if (people == 0)
							break;
					}
					if (p[i] + j <= n) { // lan chinh o do va lan phai sau 
						if (check[p[i] + j] == 0) {
							check[p[i] + j] = i;
							value += j + 1;
							people--;
						}
						if (people == 0)
							break;
					}

					j++;
				}

				solve2(count + 1, value);

				visit[i] = 0;
				for (j = 1; j <= n; j++)
					if (check[j] == i)
						check[j] = 0;
			}
		}
	}

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

		
		System.setIn(new FileInputStream("w4wed/hugo_di_tau/input_di_tau.txt"));
		Scanner sc = new Scanner(System.in) ;
		int T = sc.nextInt() ;
		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt() ; // nhap so vi tri 
			p = new int[4] ;
			c = new int[4] ;
			res = Integer.MAX_VALUE ;
			for (int i = 1; i <= 3; i++) {
				p[i] = sc.nextInt() ; // toa do con tau
				c[i] = sc.nextInt() ; // so luong nguoi cho tai moi cua
			}
			check = new int[n+1] ; 
			visit = new int[4] ;
			solve1(0 , 0) ;
			solve2(0 , 0) ;
			System.out.println("Case #" + tc); 
			System.out.println(res);
		}
	}
}

8.1/////////////////////////
moi an cuoi
package Moi_an_cuoi;

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

public class Solution_moi_an_cuoi {
	static int N, M ,v_start, v_end ;
	static int canh[][] = new int[1005][2] ;
	static int cnt[] = new int[105] ;
	static int canhke[][] = new int[105][105] ;
	static int res = 0;
	static int visited[] = new int[105] ;
	static int trace[] = new int[105] ;

	static int cnt_kq[] = new int[105] ;
	static int ans[] = new int[105] ;
	static int k, soLanToiDich;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("last_hope/Moi_an_cuoi/input_moi_an_cuoi.txt"));
		Scanner sc = new Scanner(System.in) ;
		int T = sc.nextInt() ;
		for (int tc = 1; tc <= T ; tc++) {
			soLanToiDich = 0 ;
			res = 0;
			N = sc.nextInt() ; // n dinh
			M = sc.nextInt() ; // m duong di
			v_start = sc.nextInt() ;
			v_end = sc.nextInt() ;
			
			for (int i = 0; i <= N; i++) {
				cnt[i] = 0 ;
				visited[i] = 0 ;
				ans[i] = 0 ;
			}
			
			for(int i = 0; i < M; i++){
				canh[i][0] = sc.nextInt() ;
				canh[i][1] = sc.nextInt() ;
				canhke[canh[i][0]][cnt[canh[i][0]]++] = canh[i][1] ;
			}
			visited[v_start] = 1;
			trace[0] = v_start ;
			dfs(v_start, 1) ;
			for (int i = 0; i <= N; i++) {
				if( ans[i] == soLanToiDich){
					res++ ;
				}
			}
			System.out.println(res - 2);
			System.out.println();
		}
	}

	private static void dfs(int u, int count) {
		if( u == v_end){
			for (int i = 0; i < count ; i++) {
				ans[trace[i]]++ ;
			}
			soLanToiDich++; 
			return ;
		}
		
		for (int i = 0; i < cnt[u] ; i++) {
			if( visited[canhke[u][i]] == 0){
				visited[canhke[u][i]] = 1 ;
				trace[count] = canhke[u][i] ;
				
				dfs(canhke[u][i], count + 1) ;
				trace[count] = 0;
				visited[canhke[u][i]] = 0;
			}
		}
		
	}
}

8.2///////////////
di an cuoi 
package di_an_cuoi;

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

public class Solution_di_an_cuoi {
	static int N, M ,res;
	static int cnt[] = new int[22] ; 
	static int canh[][] = new int[150][2] ;
	static int visited1[] = new int[22] ;
	static int visited2[] = new int[22] ;
	 
	static int map[][] = new int[25][25] ;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("last_hope/di_an_cuoi/input_di_an_cuoi.txt"));
		Scanner sc = new Scanner(System.in) ;
		int T = sc.nextInt() ;
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt() ;
			M = sc.nextInt() ;
			res = Integer.MAX_VALUE ;
			for (int i = 0; i <= N; i++) {
				cnt[i] = 0 ;
				visited1[i] = visited2[i] = 0 ;
			}
			
			for (int i = 0; i < M; i++) {
				canh[i][0] = sc.nextInt() ;
				canh[i][1] = sc.nextInt() ;
				map[canh[i][0]][cnt[canh[i][0]]++] = canh[i][1] ;
			}
			backtrack1_2(1) ;
			System.out.println(res);
		}
	}

	private static void backtrack1_2(int u) {
		int tmp = check() ;
		if(tmp > res){
			return ;
		}
		if( u == 2){
			backtrack2_1(u);
			return ;
		}
		for (int i = 0; i < cnt[u]; i++) {
			if( visited1[map[u][i]] == 0){
				visited1[map[u][i]] = 1;
				backtrack1_2(map[u][i]);
				visited1[map[u][i]] = 0;
			}
		}
	}

	private static void backtrack2_1(int u) {
		
		if( check() > res) {
			return ;
		}
		if( u == 1){
			int tmp = 0 ;
			for (int i = 1; i <= N; i++) {
				if( visited1[i] == 1 || visited2[i] == 2){
					tmp++ ;
				}
			}
			res = Math.min(res, tmp) ;
			return;
		}
		for (int i = 0; i < cnt[u]; i++)
		{
			
			if (visited2[map[u][i]] == 0)
			{
				visited2[map[u][i]] = 2;
				backtrack2_1(map[u][i]);
				visited2[map[u][i]] = 0;
			}
		}
	}

	private static int check() {
		int tmp = 0;
		for (int i = 1; i <= N; i++) {
			if(visited1[i] == 1 || visited2[i] == 2){
				tmp++ ;
			}
		}
		
		return tmp;
	}

}

9////////////////
bao ve nong trang
package bao_ve_nong_trang;

import java.util.Scanner;

public class Solution_bao_ve {

	static int T, N, M, result;
	static int[][] map = new int[701][701], visited = new int[701][701];
	static int[] h = { 0, 0, -1, 1, 1, 1, -1, -1 };
	static int[] v = { 1, -1, 0, 0, 1, -1, 1, -1 };
	static Scanner sc;
	static Queue<Point> q = new Queue<Point>();

	static void initialize() {
		result = 0;

		N = sc.nextInt();
		M = sc.nextInt();

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

		q.reset();
	}

	public static void main(String[] args) {


		sc = new Scanner(System.in);

		T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++) {
			// initializing variables
			initialize();

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (visited[i][j] == 0)
						find(i, j);
				}
			}

			// show result
			System.out.println("#" + test_case + " " + result);
		}


	}

	static void find(int x, int y) {
		q.enqueue(new Point(x, y));
		visited[x][y] = 1;

		boolean isTop = true;
		while (!q.isEmpty()) {
			Point p = q.dequeue();

			for (int i = 0; i < 8; i++) {
				int newX = p.x + h[i];
				int newY = p.y + v[i];

				if (newX < 0 || newX >= N || newY < 0 || newY >= M)
					continue;
				
				if (map[newX][newY] > map[p.x][p.y])
					isTop = false;

				if (visited[newX][newY] == 0
						&& map[newX][newY] == map[p.x][p.y]) {

					visited[newX][newY] = 1;
					q.enqueue(new Point(newX, newY));
				}
			}
		}
		if (isTop)
			result++;
	}

}

class Point {
	int x, y;

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

class Queue<T> {

	private static final int MAX_SIZE = 1000000, DEFAULT_INDEX = -1;
	private T[] arr;
	private int front, rear, size;

	Queue() {
		arr = (T[]) new Object[MAX_SIZE];
		front = rear = DEFAULT_INDEX;
		size = 0;
	}

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

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

	int getSize() {
		return size;
	}

	void enqueue(T value) {
		if (isFull()) {
			throw new IllegalStateException("\nQueue is filled!");
		}
		arr[++rear] = value;
		size++;
	}

	T dequeue() {
		if (isEmpty()) {
			throw new IllegalStateException("\nQueue is empty!");
		}

		T frontValue = arr[++front];
		size--;

		if (isEmpty()) { // reset queue if possible
			reset();
		}

		return frontValue;
	}

	void reset() {
		front = rear = DEFAULT_INDEX;
	}
}

10///////////////
hugo thi chay
package hugo_thi_chay;

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

public class Solution_hugo_thi_chay {
	static int M, D;
	static int phut[], giay[], nangLuong[];
	static int time[];
	static int timeMin;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream(
				"last_hope/hugo_thi_chay/input_hugo_thi_chay.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			M = sc.nextInt();// nang luong toi da
			D = sc.nextInt();// chieu dai quang duong
			phut = new int[5+1];
			giay = new int[5+1];
			nangLuong = new int[5+1];
			time = new int[5+1];
			for (int i = 1; i <= 5; i++) {
				phut[i] = sc.nextInt();
				giay[i] = sc.nextInt();
				nangLuong[i] = sc.nextInt();
			}
			// mang luu thoi gian
			for (int i = 1; i <= 5; i++) {
				time[i] = phut[i] * 60 + giay[i];
			}
			timeMin = Integer.MAX_VALUE;
			// thoi gian ngan nhat de ve ma khong bi benh
			// neu ko ve duoc in ra -1
			backtrack(1, M, 0, D);
			
			System.out.println("Case #" + tc);
			
			if( timeMin == Integer.MAX_VALUE){
				System.out.println(-1);
			} else {
				int ansPhut = timeMin / 60 ;
				int ansGiay = timeMin % 60 ;
				System.out.println( ansPhut + " " + ansGiay);
			}
		}
	}

	private static void backtrack(int kieuChay, int energy, int tg,
			int quangDuong) {
		if( tg > timeMin){
			return ; 
		}
		if( energy <= 0){
			return ; 
		}
		if( kieuChay >= 6){
			return ;
		}
		if(quangDuong <= 0){
			timeMin = Math.min(timeMin, tg) ;
			return ;
		}
		
		
		for (int j = 0; j < 2; j++) {
			if( j == 1 ){//dang chon kieu chay nay 
				//moi kieu chay chay 1km 1 lan
				//backtrack(kieuChay+1, energy - nangLuong[kieuChay], tg + time[kieuChay], quangDuong-1);
				backtrack(kieuChay, energy - nangLuong[kieuChay], tg + time[kieuChay], quangDuong - 1);
			}
			else{
				backtrack(kieuChay + 1, energy, tg, quangDuong);
			}
		}
	}
}
11////////////////
hugo ban dau
#include<iostream>
using namespace std;
int T;
int N, M;
int x_hugo, y_hugo;
int the_luc;
int map[50][50];
int check[50][50];
int osR[4]={0,1,0,-1};
int osC[4]={1,0,-1,0};
int ong_nuoc[8][4]= {
		{0, 0, 0, 0}, // left right up down
		{1, 1, 1, 1},
		{0, 1, 0, 1},
		{1, 0, 1, 0},
		{0, 1, 1, 0},
		{0, 0, 1, 1},
		{1, 0, 0, 1},
		{1, 1, 0, 0}
};
int max_h;

int queue[5000];
int rear, front;

void initQueue(){
	rear= front=-1;
}
void QueuePush(int value){
	rear++;
	queue[rear]= value;
}
int QueuePop(){
	front++;
	return queue[front];
}
bool isEmpty(){
	return front>= rear;
}


void BFS(int x_start, int y_start){
	initQueue();
	QueuePush(x_start);
	QueuePush(y_start);
	check[x_start][y_start]=1;
	while (!isEmpty() )
	{
		int curR= QueuePop();
		int curC= QueuePop();
		for(int i=0; i<8; i++){
			if(map[curR][curC]==i){
				for(int j=0; j<4; j++){
					if(ong_nuoc[i][j]==1){
						int x= curR - osR[j];
						int y= curC - osC[j];
						
						if(x>=0 && x<N && y>=0 && y<M && map[x][y]!=0 &&((ong_nuoc[map[x][y]][j+2]==1 && j+2<4) || ong_nuoc[map[x][y]][j-2]==1 && j-2 >=0 ) && check[x][y]==0){
							QueuePush(x);
							QueuePush(y);
							check[x][y]= check[curR][curC] + 1;
						}
					}
				}
			}
		}

	}
}


int main(){
	freopen("input.txt","r", stdin);
	cin>> T;
	for(int tc=1; tc<=T; tc++){
		cin >> N >> M >> x_hugo >> y_hugo >> the_luc;
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				cin>> map[i][j];
			}
		}
		//reset check
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				check[i][j]=0;
			}
		}
		
		max_h=0;
		BFS(x_hugo, y_hugo);
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				if(check[i][j]<=the_luc && check[i][j] !=0){
					max_h++;
				}
			}
		}
		

		cout<<"Case #"<<tc<<endl;
		cout<<max_h <<endl;
		
	}

	return 0;
}


12/////////////////////////////////////////
chess rock
package chess_rock;

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

public class Solution_rock {
	static int T , n;
	static int cnt, max; 
	static char[][] map = new char[4][4];
	

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/chess_rock/input_rock.txt"));
		
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt(); 
		for (int tc = 1; tc <= T; tc++) {

			n = scanner.nextInt(); // Kích thước của bàn cờ
		
			for (int i = 0; i < n; i++) {
				String input = scanner.next();
				for (int j = 0; j < n; j++) {
					map[i][j] = input.charAt(j);
					
				}
			}
			max = 0;
			cnt = 0;
			backtrack(0, 0);
			System.out.println("Case #" + tc);
			System.out.println(max);
		}
	}

	public static void backtrack(int k, int cnt) {

		if (k == n * n) { // Đã duyệt hết tất cả các dòng
			max = max > cnt ? max : cnt;
			return;
		}
			int r = k / n; // toa do hang
			int c = k % n; // toa do cot 
			for (int i = 0; i < 2; i++) {
				if (i == 1 && check(r, c)) {
					map[r][c] = 'R';
					backtrack(k+1, cnt+1);
					map[r][c] = '.';
				} else if ( i== 0)
					backtrack(k + 1, cnt);
			}

	}

	public static boolean check(int r, int c) {

		// Kiểm tra cột

		if (map[r][c] == 'X') {
			return false;
		}

		for (int i = c - 1; i >= 0; i--) {
			if (map[r][i] == 'R') {
				return false;
			}
			if (map[r][i] == 'X') {
				break;
			}
		}
		for (int i = r - 1; i >= 0; i--) {
			if (map[i][c] == 'R') {
				return false;
			}
			if (map[i][c] == 'X') {
				break;
			}
		}
		return true;
	}
}


13/////////////////////
hugo quang cao
package hugo_xep_lich_quang_cao;

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

public class Solution_xep_lich_qc {
	static int N, start, end, ans;
	static int L[] = new int[3]; // do dai quang cao
	static int P[] = new int[3]; // diem quang cao
	static int timeKhachHang[][];
	static int visit_ads[];
	static int score[][] = new int[3][51];

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream(
				"last_hope/hugo_xep_lich_quang_cao/input_xep_lich_qc.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt(); // so khach truy cap

			for (int i = 0; i < 3; i++) {
				L[i] = sc.nextInt();
			}
			for (int i = 0; i < 3; i++) {
				P[i] = sc.nextInt();
			}
			timeKhachHang = new int[N][2];
			// time den, time end = time ket thuc + time luu tru
			for (int i = 0; i < N; i++) {
				timeKhachHang[i][0] = sc.nextInt();
				timeKhachHang[i][1] = sc.nextInt() + timeKhachHang[i][0];
			}

			// chon can tren duoi
			start = timeKhachHang[0][0];
			end = timeKhachHang[0][1];
			for (int i = 0; i < N; i++) {
				start = Math.min(start, timeKhachHang[i][0]);
				end = Math.max(end, timeKhachHang[i][1]);
			}
			visit_ads = new int[3*51];
			ans = 0;
			backtrack(start,end ,0);

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

	static void resetVisit() {
		for (int i = 0; i < visit_ads.length; i++) {
			visit_ads[i] = 0;
		}
	}

	private static boolean kiemTraVisit(int start, int end) {
		// kiem tra visit
		for (int i = start; i < end; i++) {
			if (visit_ads[i] == 1) {
				// tra ra false neu ma o do co quang cao khac roi
				return false;
			}
		}
		// neu ko co quang cao nao o do
		return true;
	}

	// xay dung ham danh visit
	private static void danhVisit(int start, int end, int visit) {
		for (int i = start; i < end; i++) {
			visit_ads[i] = visit;
		}
	}

	private static void backtrack(int start, int end, int k) {
		// backtrack theo so gio quang cao

		if (k >= 3) { // khi da dat xong 3 quang cao
			int demTong = sum();
			ans = Math.max(ans, demTong);
			
			return;
		}

		// 50 moc thoi gian quang cao
		//for (int i = 1; i <= 50; i++) {
		
		//thu gon dieu kien backtrack
		for (int i = 1; i <= 50  ; i++) {
			
			if (kiemTraVisit(i, i + L[k]) == true) {
				danhVisit(i, i + L[k], 1);
				// neu ads nam trong time khach hang thi tinh diem
				for (int j = 0; j < N; j++) {// khach hang truy cap
					if (i >= timeKhachHang[j][0]
							&& i + L[k] <= timeKhachHang[j][1])
						score[k][j] = P[k];
				}
				// cac truong hop tiep
				backtrack(start, end, k + 1);

				danhVisit(i, i + L[k], 0);// tra lai visit
				// neu ads nam trong time khach hang thi tinh diem
				for (int j = 0; j < N; j++) {
					if (i >= timeKhachHang[j][0]
							&& i + L[k] <= timeKhachHang[j][1])
						score[k][j] = 0;
				}
			}
		}
	}

	private static int sum() {
		int count = 0;

		for (int j = 0; j < N; j++) {
			int cur_max = score[0][j];
			for (int i = 0; i < 3; i++) {
				cur_max = Math.max(cur_max, score[i][j]);
			}
			count += cur_max;
		}
		return count;
	}
}

14/////////////////////////////////
hugo ve nha
#include <iostream>
using namespace std;

int T, N, G[50][2], Ans, d;

void backTrack(int step, int price,  int numOfArmy1, int numOfArmy2, int numOfArmy3){
	if (step == N)
	{
		Ans = min(Ans, price);
		return;
	}

	if (price > Ans) return;
	//for 3 lua chon: 
	//0 : pass (tra du tien -> 0 co linh).
	//1 : hire (X2 tien co linh).
	//2 : Battle (danh nhau ko mat phi -> so linh con lai = so linh - quan thu thanh).

	for (int i = 0; i < 3; i++)
	{
		if (i == 0)
			backTrack(step + 1, price + G[step][1], numOfArmy1, numOfArmy2, numOfArmy3);
		if (i == 1)
			backTrack(step + 1, price + G[step][1] * 2, numOfArmy1 + G[step][0], numOfArmy2, numOfArmy3);
		if (i == 2 && numOfArmy1 + numOfArmy2 + numOfArmy3 >= G[step][0])
		{
			if (numOfArmy3 >= G[step][0])
				backTrack(step + 1, price, 0, numOfArmy1, numOfArmy2);
			else if (numOfArmy2 + numOfArmy3 >= G[step][0])
				backTrack(step + 1, price, 0, numOfArmy1, numOfArmy2 - (G[step][0] - numOfArmy3));
			else if (numOfArmy1 + numOfArmy2 + numOfArmy3 >= G[step][0])
				backTrack(step + 1, price, 0, numOfArmy1 - (G[step][0] - numOfArmy2 - numOfArmy3), 0);
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);

	cin >> T;
	for (int TC = 1; TC <= T; TC++)
	{
		cin >> N;

		for (int i = 0; i < N; i++)
			cin >> G[i][0] >> G[i][1];

		Ans = 99999999;
		backTrack(0, 0, 0, 0, 0);
		cout << "#" << TC << " " << Ans << endl;
	}

	return 0;
}
/////////////////////////////////
15 pha huy he thong dien
import java.util.Scanner;

public class Solution {
	static int N;
	static int [][]map;
	static int []visited;
	public static class Queue{
		final int MAX_SIZE = 10000000;
		int []data = new int[MAX_SIZE];
		int front;
		int rear;
		public Queue(){
			front = rear = -1;
		}
		public void init(){
			front = rear = -1;
		}
		public boolean isEmpty(){
			if(front == rear) return true;
			else return false;
		}
		public void enQueue(int element){
			rear = rear + 1;
			data[rear] = element;
		}
		public int deQueue(){
			front = front + 1;
			return data[front];
		}
	}
	
	static Queue queue;
	public static void bfs(int dao){
		queue.init();
		queue.enQueue(dao);
		visited[dao] = 1;
		while (!queue.isEmpty()) {
			int island = queue.deQueue();
			for(int i=1; i<=N; i++){
				if(map[island][i] == 1 && visited[i] == 0){
					visited[i] = 1;
					queue.enQueue(i);
				}
			}
			
		}
	}
	
	public static void resetVisit(){
		for(int i=1; i<=N; i++){
			visited[i] = 0;
		}
	}
	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		queue = new Queue();
		int TC = scanner.nextInt();
		for(int t=0; t<TC; t++){
			N = scanner.nextInt();
			map = new int[N+1][N+1];
			for(int i=1; i<=N; i++){
				for(int j=1; j<=N; j++){
					map[i][j] = scanner.nextInt();
				}
			}
			visited = new int[N+1];
			int maxVung = 1;
			int index = -1;
			for(int i=1; i<=N; i++){
				for(int j=1; j<=N; j++){
					if(map[i][j] == 1){
						map[i][j] = 2;
						map[j][i] = 2;
					}			
				}
				resetVisit();
				visited[i] = 1;
				int count = 0;
				for(int k=1; k<=N; k++){
					if(visited[k] == 0){
						count++;
						bfs(k);
					}
				}
				if(count > maxVung){
					maxVung = count;
					index = i;
				}
				for(int j=1; j<=N; j++){
					if(map[i][j] == 2){
						map[i][j] = 1;
						map[j][i] = 1;
					}			
				}
			}
			if(index == -1){
				System.out.println(0);
			}
			else{
				System.out.println(index);
			}
			
			
//			for(int i=0; i<=N; i++){
//				for(int j=0; j<=N; j++){
//					System.out.print(map[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();
		}
	}
}
16////////////////////
tiet kiem dien
package power_saving;

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

public class Solution_tiet_kiem_dien {
	static int N, K, max, curMax, cnt;
	static int statusLamp[] ;
	static int kControll[][] ;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream(
				"last_hope/power_saving/input_power_saving.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			K = sc.nextInt();
			max = 0;
			statusLamp = new int[N + 1];
			kControll = new int[K + 1][K + N * (K + 1)];
			for (int i = 1; i <= N; i++) {
				statusLamp[i] = sc.nextInt();
				max = demSoBongDenTat();
			}

			// 1 -->k + n * (k+1) ;
			// luu trang thai khoa K
			// vs k = i dieu khien bong den i + k(k + i) .
			for (int k = 1; k <= K; k++) {
				for (int i = 0; i <= N; i++) {
					if (k + i * (k + 1) <= N) {
						kControll[k][k + i * (k + 1)] = 1;

					}
				}
			}
			//printLamp();
			cnt = 0;
			// backtrack
			backtrack(1);
			System.out.println("#" + tc + " " + max);
		}
	}

	private static void printLamp() {
		for (int u = 1; u <= K; u++) {
			for (int v = 1; v <= N; v++) {
				System.out.print(kControll[u][v] + " ");
			}
			System.out.println();
		}
		System.out.println();

	}

	// backtrack theo khoa k
	private static void backtrack(int k) {
		// dk dung: chi duoc 3 lan thay doi khoa
		if (cnt > 3) {
			return;
		}
		if (k == K + 1) {
			max = demSoBongDenTat() > max ? demSoBongDenTat() : max;
			return;
		}

		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				for (int j = 1; j <= N; j++) {
					if (kControll[k][j] == 1) {
						statusLamp[j] = 1 - statusLamp[j];
					}
				}
				cnt++;
				backtrack(k + 1);
				cnt--;
				for (int j = 1; j <= N; j++) {
					if (kControll[k][j] == 1) {
						statusLamp[j] = 1 - statusLamp[j];
					}
				}
			} else {
				backtrack(k + 1);
			}
		}
	}

	private static int demSoBongDenTat() {
		int cntLampOff = 0;
		for (int i = 1; i <= N; i++) {
			if (statusLamp[i] == 0) {
				cntLampOff++;
			}
		}
		return cntLampOff;
	}

}


17//////////////////
nuoc bien
#include <iostream>
using namespace std;

int T, N, M, data[100][100], temp[100][100], top, minn, maxx, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, ans, hMax;
int visited[100][100];
struct Pos {int r, c;};
Pos stack[100000];
void push(int rr, int cc) {
	top++; Pos p; p.r = rr; p.c = cc;
	stack[top] = p;
}
Pos pop() {Pos ret = stack[top]; top--; return ret;}

void loang(int r, int c) {
	top = -1;
	push(r, c);
	temp[r][c] = 1;
	while (top > -1) {
		Pos p = pop();
		for (int i = 0; i < 4; i++) {
			int newH = p.r + dx[i];
			int newC = p.c + dy[i];
			if (newH >= 0 && newH < N && newC >= 0 && newC < M && data[newH][newC] <= hMax && temp[newH][newC] == 0) {
				push(newH, newC);
				temp[newH][newC] = 1;
			}
		}
	}
}

void dfs(int r, int c) {
	top = -1;
	push(r, c);
	visited[r][c] = true;
	while (top > -1) {
		Pos p = pop();
		for (int i = 0; i < 4; i++) {
			int newH = p.r + dx[i];
			int newC = p.c + dy[i];
			if (newH >= 0 && newH < N && newC >= 0 && newC < M && visited[newH][newC] == false && temp[newH][newC] == 0) {
				push(newH, newC);
				visited[newH][newC] = true;
			}
		}
	}
}

int main(){
	//freopen("input.txt" , "r" , stdin);
	T = 0;
	while (true) {
		cin >> N >> M;
		T++;
		int ans;
		maxx = 0; minn = 1001;
		bool check = false;
		if (N == 0 && M == 0)
			break;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> data[i][j];
				if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
					maxx = maxx < data[i][j] ? data[i][j] : maxx;
					minn = minn > data[i][j] ? data[i][j] : minn;
				}
			}
		}
		for (int k = minn; k <= maxx; k++) {
			hMax = k;
			for (int i = 0; i < N; i++)
				for (int j = 0; j < M; j++) 
					temp[i][j] = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
						if (data[i][j] <= hMax && temp[i][j] == 0)
							loang(i, j);
					}
				}
			}
			int dem = 0;
			for (int i = 0; i < N; i++)
				for (int j = 0; j < M; j++) 
					visited[i][j] = false;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (temp[i][j] == 0 && visited[i][j] == false) {
						dem++;
						if (dem > 1)
							break;
						dfs(i, j);
					}
				}
				if (dem > 1)
					break;
			}
			if (dem > 1) {
				check = true;
				break;
			}
		}
		if (!check)
			cout << "Case " << T << ": Island never splits." << endl;
		else {
			cout << "Case " << T << ": Island splits when ocean rises " << hMax << " feet." << endl;
		}
	}
	return 0;
}

18//////////////////////////////
battel city
#include<iostream>
using namespace std;
int T;
int M, N;
char map[301][301];
long long visited[301][301];
int x_end, y_end;
int x_start, y_start;

int osR[4]= {1,0,-1,0};
int osC[4]= {0,1,0,-1};
int queue[600010];
int rear,front;

void initQueue(){
	rear= front= -1;
}
void QueuePush(int value){
	rear++;
	queue[rear]=value;
}
int QueuePop(){
	front++;
	return queue[front];
}
bool isEmpty(){
	return front>=rear;
}


void BFS(int x_start, int y_start){
	
	initQueue();
	QueuePush(x_start);
	QueuePush(y_start);
	visited[x_start][y_start]= 1;
	while (!isEmpty())
	{
	
		int curR= QueuePop();
		int curC= QueuePop();
		for(int i=0; i<4; i++){
			int x= curR + osR[i];
			int y= curC + osC[i];
			if(x>=0 && x<M && y>=0 && y<N && ( map[x][y]=='E' ||  map[x][y]=='T')&& visited[x][y] > visited[curR][curC] + 1){
				//tiep code
				QueuePush(x);
				QueuePush(y);
				visited[x][y]= visited[curR][curC] + 1;
			}
			if(x>=0 && x<M && y>=0 && y<N && map[x][y]=='B' && visited[x][y] > (visited[curR][curC] + 2) ){
				//tiep code
				QueuePush(x);
				QueuePush(y);
				visited[x][y]= visited[curR][curC] + 2;
			}
			
		}
	}
}

int main(){
	freopen("input.txt","r", stdin);
	cin>>T;
	for(int tc=1; tc<=T; tc++){
		cin>> M >> N;
		for(int i=0; i<M; i++){
			for(int j=0; j<N; j++){
				cin>>map[i][j];
				if(map[i][j]=='Y'){
					x_start=i;
					y_start=j;
					visited[i][j]=1;
				}
				if(map[i][j]=='T'){
					x_end=i;
					y_end=j;
					visited[i][j]=10000;
				}
				
				if(map[i][j]=='B' ){
					visited[i][j]=10000;
				}
				if(map[i][j]=='E' ){
					visited[i][j]=10000;
				}
			}
		}
		
	
		//log
		/*cout<<"visited 1:"<<endl;
		for(int i=0; i<M; i++){
			for(int j=0; j<N; j++){
				cout<<visited[i][j]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;*/
		
		BFS(x_start, y_start);
		
		if(visited[x_end][y_end]!=10000){
			cout<<"Case #"<<tc<<endl;
			cout<< visited[x_end][y_end] - 1 <<endl;
		}else
		{
			cout<<"Case #"<<tc<<endl;
			cout<<  -1 <<endl;
		}
		//log
		
	}
	return 0;
}

19///////////////////////
frog
package The_Frog;

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

public class Solution_frog {

	static final int INF = 200000000;

	static int T, N, result;
	static int[][] map;
	static int[][] pos;
	static int[] rad;

	static int[] distance, visit;
	static int gan, xa, ret;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/The_Frog/input_frog.txt"));
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();

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

			map = new int[N][N];

			pos = new int[N][2];
			rad = new int[N];

			distance = new int[N];
			visit = new int[N];

			for (int i = 0; i < N; i++) {
				distance[i] = INF;
				visit[i] = 0;
				for (int j = 0; j < N; j++) {
					map[i][j] = 0;
				}
			}

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

			int ret = 0;

			for (int i = 0; i < N; i++) {
				for (int j = i + 1; j < N; j++) {
					ret = pow(pos[i][0] - pos[j][0])
							+ pow(pos[i][1] - pos[j][1]);
					if (ret <= pow(40 + rad[i] + rad[j])) {
						map[i][j] = 1;
					} 
					else if ((ret > pow(40 + rad[i] + rad[j]))
							&& ret <= pow(90 + rad[i] + rad[j])) {
						map[i][j] = 200;
					} 
					else if (ret > pow(90 + rad[i] + rad[j])) {
						map[i][j] = INF;
					}
					map[j][i] = map[i][j];
				}
			}

			Dijkstra(0);
			ret = distance[N - 1];
			// show result
			if (ret != INF) {
				gan = ret / 200;
				xa = ret % 200;
				System.out.println(gan + " " + xa);
			} else {
				System.out.println(-1);
			}
		}
	}

	private static void Dijkstra(int start) {
		distance[start] = 0;

		for (int i = 0; i < N; i++) {
			int u = minDistance();
			visit[u] = 1;

			for (int j = 0; j < N; j++) {
				if (map[u][j] != INF && visit[j] == 0 && map[u][j] != 0) {
					if (map[u][j] + distance[u] < distance[j]) {
						distance[j] = map[u][j] + distance[u];
					}
				}
			}
		}
		
		

	}

	private static int minDistance() {
		int min = INF;
		int index = 0;
		for (int i = 0; i < N; i++) {
			if (distance[i] <= min && visit[i] == 0) {
				min = distance[i];
				index = i;
			}
		}
		return index;
	}

	private static int pow(int val) {
		return val * val;
	}
}

20///////
map coloring
import java.util.Scanner;

public class Solution {
	static int N, E;

	static final int max_n = 1005;
	static final int max_int = Integer.MAX_VALUE ;
	static int maTranKe[][] = new int[max_n][max_n];
	static int color[] = new int[max_n];
	static int visit[] = new int[max_n];
	static int countColored;

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("src/map_color/input_color.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

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

			for (int i = 1; i <= N; i++) {
				color[i] = -1;
				maTranKe[i][0] = 0;
				visit[i] = 0;
			}

			int a, b;
			for (int i = 1; i <= E; i++) {
				a = sc.nextInt();
				b = sc.nextInt();
				maTranKe[a][++maTranKe[a][0]] = b;
				maTranKe[b][++maTranKe[b][0]] = a;
			}

			// solution	
			color[1] = 0; // mau dau tien la mau do : 0
			visit[1] = 1;
			countColored = 1;
			DFS(1);

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

	private static void DFS(int curentCountry) {
		int nextCountry;
		for (int i = 1; i <= maTranKe[curentCountry][0]; i++) {
			nextCountry = maTranKe[curentCountry][i];
			if (visit[nextCountry] == 0) {
				// Trả về giá trị là 1 nếu chỉ một trong các toán hạng là 1 
				//và trả về 0 trong các trường hợp khác.
				if (isSafe(nextCountry, color[curentCountry] ^ 1 )) {
					color[nextCountry] = color[curentCountry] ^ 1;

					countColored++;
					visit[nextCountry] = 1;
					DFS(nextCountry);
				}
			}
		}

	}

	public static boolean isSafe(int country, int mauHienTai) {
		for (int i = 1; i <= maTranKe[country][0]; i++) 
		{
			if (visit[maTranKe[country][i]] == 1) 
			{
				if (color[ maTranKe[country][i] ] == mauHienTai) 
				{

					return false;
				}
			}
		}
		return true;
	}

}
21////////////////
shinwa
#include <iostream>
using namespace std;
int N,M;
char map[100][100];

int visited[100][100];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int start_x,start_y;
int flag=0;
void nhapmap()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin>> map[i][j];
			
		}
	}
}

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

int inBound(int x, int y)
{
	if (1<=x && x<=N && 1<=y && y<=M)
	{
		return 1;
	}
	return 0;
}




void dfs(int x,int y, int count   )
{   
	for (int k = 0; k < 4; k++)
	{
		int new_x= x+dx[k];
		int new_y= y+dy[k];
		
		if ( inBound(new_x,new_y)  && map[new_x][new_y]==map[x][y]    )
		{
			
			if (visited[new_x][new_y]==0)
			{
			visited[new_x][new_y]=1+visited[x][y];
			
			dfs(new_x,new_y,count+1);
			
			
			}
			else if (visited[new_x][new_y]!=0 
			&& visited[new_x][new_y]+1< visited[x][y]
			&&count >=4 )
			{
				flag =1;
				
			}
			
		}
	}


}




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

	int T; cin >> T;
	
	for (int tc = 1; tc <= T; ++tc)
	{   
		cin>>N>>M;
		nhapmap();
		resetVisited();
		
	
		 flag=0;
		int level=1000;
		
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= M; j++)
			{
				if (visited[i][j]==0)
				{      
					   visited[i][j]=level;
					   dfs(i,j,1);
					
						if(flag==1)
						break;
					
					level--;

				}
				
			}
			if (flag ==1)
			{
				break;
			}

		}

		if (flag ==1)
		{
			cout <<"Case "<<tc<<":"<<" YES"<<endl;
		}else
			cout <<"Case "<<tc<<":"<<" NO"<<endl;

	}

	return 0;
}
///////////////
22
littel elephant
package littel_elephant;

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

public class Solution_lit_elephant {
	static int T, N, M, K, result;
	static final int INF = Integer.MAX_VALUE ;
	static int[] R = new int[17];


	static int backtrack(int idx, int change, int[] temp){
		if( idx == N){
			if( !kiemTraMax(temp) ){
				return change ;
			}
			return INF ;
		}
		
		for (int i = 0; i <= 1; i++) {
			temp[idx] = R[idx] + i ;//thay doi ket qua
			//lua chon tiep 
			int a = backtrack(idx +1, change+ i, temp) ;
			result = result < a ? result : a ;
		}
		return result ;
	}

	static boolean kiemTraMax(int[] R){
		for (int i = 0; i <= N - K; i++) {
			int max = 0;
			for (int j = i; j <= i + K -1; j++) {
				if( max < R[j]){
					max = R[j] ;
				}
			}
			int count = 0 ;//dem xem co bn phan tu max
			for (int j = i; j <= i + K - 1; j++) {
				if( R[j] == max){
					count++ ;
				}
			}
			if( count >= M){//co nhieu hon con voi vuot qua max
				return true; //--> bi bat
			}
		}
		return false ;// --> ko bi bat 
	}

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/littel_elephant/input_lit_ele.txt"));
		Scanner scanner = new Scanner(System.in);

		T = scanner.nextInt();

		for (int t = 1; t <= T; t++) {
			N = scanner.nextInt(); // so voi
			K = scanner.nextInt(); // xet K con voi lien tiep
			M = scanner.nextInt(); // khong duoc qua M con voi max

			for (int i = 0; i < N; i++) {
				R[i] = scanner.nextInt();
			}
			
			result = INF;
			int minThaoTac = backtrack(0, 0, new int[N]);
			if (minThaoTac == INF) {
				System.out.println("#" + t + " -1");
			} else {
				System.out.println("#" + t + " " + minThaoTac);
			}
		}

		scanner.close();
	}
}
///////////////
23 domino
package domino;

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

public class Solution_domino {
	static int T, ans;
	static int map[][] = new int[7][8];
	static int visited[][] = new int[7][8];
	static int used[][] = new int[7][7];

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/domino/input_domino.txt"));
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {

			for (int i = 0; i < 7; i++) {
				for (int j = 0; j < 8; j++) {
					map[i][j] = sc.nextInt();
					visited[i][j] = 0;

				}
			}

			for (int i = 0; i < 7; i++) {
				for (int j = 0; j < 7; j++) {
					used[i][j] = 0;
				}
			}
			ans = 0;
			BT(0, 0);
			System.out.println("Case #" + tc);
			System.out.println(ans);

		}
		sc.close();
	}

	public static void BT(int r, int c) {
		if (r == 6 && c == 7) {
			ans++;
			return;
		}

		if (visited[r][c] == 0) {
			// xep doc
			
			if (r < 6 && visited[r + 1][c] == 0) {
				int num1 = map[r][c];
				int num2 = map[r + 1][c];
				if (used[num1][num2] == 0) {
					visited[r][c] = visited[r + 1][c] = 1;
					used[num1][num2] = used[num2][num1] = 1;
					if (c < 7) {
						BT(r, c + 1);
					} else {
						BT(r + 1, 0);
					}

					visited[r][c] = visited[r + 1][c] = 0;
					used[num1][num2] = used[num2][num1] = 0;
				}
			}

			// xep ngang
			if (c < 7 && visited[r][c + 1] == 0) {
				int num1 = map[r][c];
				int num2 = map[r][c + 1];
				if (used[num1][num2] == 0) {
					visited[r][c] = visited[r][c + 1] = 1;
					used[num1][num2] = used[num2][num1] = 1;
					BT(r, c + 1);

					visited[r][c] = visited[r][c + 1] = 0;
					used[num1][num2] = used[num2][num1] = 0;
				}
			}

			// duyet theo hang

		} else {
			if (c < 7) {
				BT(r, c + 1); // chua den cuoi hang
			} else {
				BT(r + 1, 0);// o dau tien hang tiep theo
			}
		}
	}

}
/////////////////////
24 painting
package painting;

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

public class Solution_painting {
    static int T, n;
    static int[][] map = new int[31][31];
    
    static int tongTruongHop;

    public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("src/painting/input_paiting.txt"));
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();
        
        for (int tc = 1; tc <= T; tc++) {
            n = scanner.nextInt();
            
            tongTruongHop = 0;
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    map[i][j] = scanner.nextInt();
                }
            }
            //backtrack
            tongTruongHop = dem4Mau(0, new int[n]);
            
            System.out.println("Case #" + tc);
            System.out.println(tongTruongHop);
        }
    }

    public static int dem4Mau(int k, int[] mangMau) {
        if (k == n) {
            return 1;
        }

        int total = 0;

        for (int color = 2; color <= 5; color++) {
			if(check(k, color, mangMau)){
				mangMau[k] = color ; 
				total = total + dem4Mau(k + 1, mangMau) ;
				mangMau[k] =  0;
			}
		}

        return total;
    }

    public static boolean check(int k, int color, int[] mangMau) {
        for (int i = 0; i < n; i++) {
            if (map[k][i] == 1 && mangMau[i] == color) {
                return false;
            }
        }
        return true;
    }
}
25/////////////////
enhance mario
#include <iostream>
using namespace std;
int N,M;
int count=0;
int arr[201];
int coins[201];
int bombs[201];
int petals[201];
bool flag;
void calculate(int post,int bomb3,int bomb2,int bomb1,int coin)
{
    int temp=0;
    if(flag) return;
    if(post==N-1)
    {
        flag=true;
        return;
    }
    if(bomb3*5+bomb2*2+bomb1<petals[post]&&coin<petals[post]) return;
    else if(bomb3*5+bomb2*2+bomb1>=petals[post]&&!flag)
    {
        if(bomb1>=petals[post]) bomb1=0;
        else if(bomb2*2+bomb1>=petals[post]) 
        {
            temp=petals[post];
            temp=temp-bomb1;
            bomb2=(bomb2*2-temp)/2;
  
        }
        else if((bomb1+bomb2*2+bomb3*5)>=petals[post])
        {
            temp=petals[post];
            temp=temp-(bomb1+bomb2*2);
            bomb3=(bomb3*5-temp)/5;
  
        }
        calculate(post+1,0,bomb3,bomb2,coin);
    }
    if(coin>=petals[post])
    {
        calculate(post+1,bombs[post],0,0,(coin+coins[post]-petals[post]));
    }
}
int main(int argc, char** argv)
{
    int T, test_case;
   // freopen("input.txt", "r", stdin); 
    cin >> T;
  
    for(test_case = 0; test_case  < T; test_case++)
    {
      flag=false;
      cin>>N;
      for(int i=0;i<N;i++)
      {
          cin>>arr[i]>>petals[i]>>coins[i]>>bombs[i];
            
      }
        calculate(0,0,0,0,0);
      cout<<"Case #"<<test_case+1<<endl;
      if(flag) cout<<"Y"<<endl;
      else cout<<"N"<<endl;
    }
    //while(1);
    return 0;
}

26//////////////
array game
package array_game;

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

public class Solution_aray_game {
	static int N;
	static long sum;
	static int a[];
	static int ans;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/array_game/input_array_game.txt"));
		Scanner scanner = new Scanner(System.in);

		int T = scanner.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = scanner.nextInt();
			a = new int[N];
			for (int i = 0; i < N; i++) {
				a[i] = scanner.nextInt();
			}
			sum = 0;
			for (int i = 0; i < N; i++) {
				sum += a[i] ;
			}
			ans = 0;
			BT(0, N, 0, sum);
			System.out.println(ans);
		}

		scanner.close();
	}

	public static void BT(int left, int right, int point, long sum) {
		if (sum == 0) {
			ans = N - 1;
			return;
		}
		if (sum % 2 != 0) { // tong le ko chia duoc 2 ben bang nhau
			//ans = Math.max(ans, point);
			ans = ans > point ? ans : point ;
			return;
		}

		if (left >= right) {
			ans = ans > point ? ans : point ;
			return;
		}

		int mid = findMid(left, right, sum / 2); // vi tri mid chia duoc 2 ben
		if (mid == -1) {
			ans = ans > point ? ans : point ;
			return;
		}
		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				BT(left, mid, point + 1, sum / 2);
			} else {
				BT(mid + 1, right, point + 1, sum / 2);
			}
		}

	}

	private static int findMid(int left, int right, long sum) {
		long curSum = 0;
		
			for (int i = left; i < right; i++) {
				curSum += a[i];
				if (curSum == sum) {
					return i ;
				}
			}
			
		return -1;
	}

}
///////////////
27
mario clim
package mario;

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

public class Solution_mario_climb {
	static int n, m;
	static int[][] a, visited;
	static int startX, startY, endX, endY;
	static int dx[] = { 0, 0, -1, 1 }; // k=0 trai,k=1 phai,k=2 di len,k=3 di
										// xuong
	static int dy[] = { -1, 1, 0, 0 };

	static class Queue {
		static int maxq = 100001;
		int data[] = new int[maxq];
		int front, rear;

		Queue() {
			front = rear = -1;
		}

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

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

		void enq(int v) {
			data[++rear] = v;
		}

		int deq() {
			return data[++front];
		}

		int peek() {
			return data[front + 1];
		}

	}

	static Queue qX = new Queue();
	static Queue qY = new Queue();

	public static void resetVisit() {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				visited[i][j] = -1;
			}
		}
	}

	public static boolean bfs(int startX, int startY, int buocNhay) {
		qX.reset();
		qY.reset();
		resetVisit();
		qX.enq(startX);
		qY.enq(startY);

		visited[startX][startY] += 1;

		boolean check = false;
		while (!qX.isE()) {
			int h = qX.deq();
			int c = qY.deq();

			for (int k = 0; k < 4; k++) {

				if (k == 0 || k == 1) { // di sang trai hoac sang phai
					int newH = h + dx[k];
					int newC = c + dy[k];
					if (newH >= 0 && newH < m && newC >= 0 && newC < n) {
						if (newH == endX && newC == endY) {
							check = true;
						}
						if (visited[newH][newC] == -1 && a[newH][newC] == 1) {
							visited[newH][newC] = visited[h][c] + 1;
							qX.enq(newH);
							qY.enq(newC);
						}
					}
				}

				else if (k == 2) {// nhay len
					for (int j = 0; j <= buocNhay; j++) {// so buoc nhay co the
															// <=
						int newH = h + j * dx[k];
						int newC = c + dy[k];
						if (newH >= 0 && newH < m && newC >= 0 && newC < n) {
							if (newH == endX && newC == endY) {
								check = true;
							}
							if (visited[newH][newC] == -1 && a[newH][newC] == 1) {
								visited[newH][newC] = visited[h][c] + 1;
								qX.enq(newH);
								qY.enq(newC);
							}
						}
					}
				} else if (k == 3) {// nhay xuong
					for (int j = 0; j <= buocNhay; j++) {
						int newH = h + j*dx[k];
						int newC = c + dy[k];
						if (newH >= 0 && newH < m && newC >= 0 && newC < n) {
							if (newH == endX && newC == endY) {
								check = true;
							}
							if (visited[newH][newC] == -1 && a[newH][newC] == 1) {
								visited[newH][newC] = visited[h][c] + 1;
								qX.enq(newH);
								qY.enq(newC);
							}
						}
					}
				}
			}
			if (check == true) {
				break;
			}
		}
		return check;
	}

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

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

			m = sc.nextInt();
			n = sc.nextInt();
			a = new int[m][n];
			visited = new int[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					a[i][j] = sc.nextInt();
				}
			}

			// xu ly BFS

			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if (a[i][j] == 2) {
						startX = i;
						startY = j;
					}
					if (a[i][j] == 3) {
						endX = i;
						endY = j;
					}
				}
			}

			int res = -1;
			for (int i = 0; i < n; i++) {
				if (bfs(startX, startY, i)) {
					res = i;
					break;
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(res);

			// for (int i = 0; i < m; i++) {
			// for (int j = 0; j < n; j++) {
			// System.out.print(a[i][j] + " ");
			// }
			// System.out.println();
			// }
			// System.out.println();
			//
			// for (int i = 0; i < m; i++) {
			// for (int j = 0; j < n; j++) {
			// System.out.print(visited[i][j] + " ");
			// }
			// System.out.println();
			// }
			// System.out.println();
		}
	}
}
///////////////
28 hugo dem vung
package hugo_dem_vung;

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

public class Solution_hugo_dem_vung {
	static final int max_n = 101;
	static int T, N, maxRes, xRes, yRest, countRes, Region;
	static int[][] map = new int[max_n][max_n];
	static int[][] visited = new int[max_n][max_n];
	static int[][] visited1 = new int[max_n][max_n];
	static int[] Dx = { 0, -1, 0, 1 };
	static int[] Dy = { -1, 0, 1, 0 };
	static MyQueue<Integer> queue = new MyQueue<Integer>(max_n * max_n * 3);

	static void resetvidited1() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				visited1[i][j] = 0;
			}
		}
	}

	static void resetvidited() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				visited[i][j] = 0;
			}
		}
	}

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

	static void BFS(int r, int c, int region) {
		int count = 0;
		int newR, newC;
		queue.reset();
		queue.enQueue(r);
		queue.enQueue(c);
		visited1[r][c] = region;
		visited[r][c] = 1;
		while (!queue.isEmpty()) {
			r = queue.deQueue();
			c = queue.deQueue();
			for (int i = 0; i < 4; i++) {
				newR = r + Dx[i];
				newC = c + Dy[i];
				if (newR < 0 || newR >= N || newC < 0 || newC >= N
						|| visited[newR][newC] == 1)
					continue;
				if (visited1[newR][newC] == 0 && map[r][c] == 0) {
					if (map[newR][newC] == 0 || map[newR][newC] == region) {
						visited1[newR][newC] = region;
						queue.enQueue(newR);
						queue.enQueue(newC);
						count++;
					}
				} else if (visited1[newR][newC] == 0 && map[r][c] == region
						&& visited[newR][newC] == 0) {
					if (map[newR][newC] == region) {
						visited1[newR][newC] = region;
						queue.enQueue(newR);
						queue.enQueue(newC);
						count++;
					}
				}
			}
		}

		if (maxRes <= count) {
			maxRes = count;
			Region = region;
		}
	}

	static void BFSfill(int r, int c, int region) {
		int newR, newC;
		queue.reset();
		queue.enQueue(r);
		queue.enQueue(c);
		visited1[r][c] = region;
		map[r][c] = region;
		visited[r][c] = 1;
		while (!queue.isEmpty()) {
			r = queue.deQueue();
			c = queue.deQueue();
			for (int i = 0; i < 4; i++) {
				newR = r + Dx[i];
				newC = c + Dy[i];
				if (newR < 0 || newR >= N || newC < 0 || newC >= N)
					continue;
				if (visited1[newR][newC] == 0) {
					if (map[newR][newC] == 0) {
						visited1[newR][newC] = region;
						visited[newR][newC] = 1;
						queue.enQueue(newR);
						queue.enQueue(newC);
						map[newR][newC] = region;
					}
				}
			}
		}
	}

	static void BFSCount(int r, int c) {
		int newR, newC;
		queue.reset();
		queue.enQueue(r);
		queue.enQueue(c);
		int region = map[r][c];
		visited1[r][c] = region;
		while (!queue.isEmpty()) {
			r = queue.deQueue();
			c = queue.deQueue();
			for (int i = 0; i < 4; i++) {
				newR = r + Dx[i];
				newC = c + Dy[i];
				if (newR < 0 || newR >= N || newC < 0 || newC >= N)
					continue;
				if (visited1[newR][newC] == 0) {
					if (map[newR][newC] == region) {
						visited1[newR][newC] = region;
						queue.enQueue(newR);
						queue.enQueue(newC);
					}
				}
			}
		}
	}

	static void fill0() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0) {
					maxRes = 0;
					for (int k = 1; k < 6; k++) {
						resetvidited1();
						BFS(i, j, k);

					}
					resetvidited1();
					BFSfill(i, j, Region);
				}
			}
		}
	}

	static int Solution1() {
		int count = 0;
		fill0();
		resetvidited1();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited1[i][j] == 0) {
					BFSCount(i, j);
					count++;
				}
			}
		}
		return count;
	}

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

		T = sc.nextInt();
		for (int testcase = 1; testcase <= T; testcase++) {
			N = sc.nextInt();
			resetvidited1();
			resetvidited();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			System.out.println("Case #" + testcase);
			System.out.println(Solution1());

		}

	}
}

class MyQueue<T> {
	private int front;
	private int rear;
	private int size;
	private int capacity;
	private T[] queue;

	public MyQueue(int Capacity) {
		this.capacity = Capacity;
		queue = (T[]) new Object[Capacity];
		front = 0;
		rear = -1;
		size = 0;
	}

	public void enQueue(T e) {
		rear = (rear + 1) % capacity;
		queue[rear] = e;
		size++;

	}

	public T deQueue() {
		T e = queue[front];
		front = (front + 1) % capacity;
		size--;
		return e;
	}

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

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

/////////////////
29 prime ring
package prime_ring;

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

public class prime_ring {
	static int n, T, cnt;
	static long start, end;
	static int[] numbers;
	static int[] result;
	static boolean[] visited;

	// static boolean[] isPrime = new boolean[2*17+1]; // sang so nguyen tp

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

		T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt();
			numbers = new int[n];
			result = new int[n];
			visited = new boolean[n];
			for (int i = 0; i < n; i++) {
				numbers[i] = sc.nextInt();
			}

			cnt = 0;
			result[0] = numbers[0];
			bt(1);

			System.out.println("Case " + tc + ": " + cnt);
		}

	}

//	public static boolean laSoNguyenTo(int num) {
//		if (num == 1) return false;
//		if (num == 2) return true;
//
//		for (int i = 2; i * i < num; i++) {
//			if (num % i == 0) return false;
//		}
//		return true;
//	}

	public static boolean laSoNguyenTo(int num) {
		if (num == 1)
			return false;
		if (num == 2)
			return true;

		for (int i = 2; i * i <= num; i++) {
			if (num % i == 0)
				return false;
		}
		return true;
	}
	
	public static void bt(int k) {
		if (k == n) {
			if (laSoNguyenTo(result[k - 1] + result[0])) {
				cnt++;
			}
			return;
		}

		for (int i = 1; i < n; i++) {
			if (visited[i] == false) {
				result[k] = numbers[i];
				visited[i] = true;
				if (laSoNguyenTo(result[k] + result[k - 1])) {
					bt(k + 1);
				}
				result[k] = 0;
				visited[i] = false;

			}
		}
	}

}

///////////////////////
30 
tan cong thanh tri

package tan_cong_thanh_tri;

//tan cong thanh tri
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution_tan_cong_thanh_tri {
	static final int mx = 101;
	static int T, tc;
	static int m; // số đỉnh
	static int a, b, c;
	static int d;
	static int[] mangMayBanDa = new int[mx];
	static int[][] maTranKe = new int[mx][mx];
	static int[] visit = new int[mx];
	static int[] parents = new int[mx];
	static int kqvong;
	static int result;
	static int startVong;
	static int endVong;
	static int minMayBanDa;
	static long start, end;

	// reset
	static void reset() {
		kqvong = 0;
		result = 0;
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= m; j++) {
				maTranKe[i][j] = 0;
			}
		}
		for (int i = 1; i <= m; i++) {
			visit[i] = 0;
			mangMayBanDa[i] = 0;
			parents[i] = -1;
		}
	}

	// Tìm đường đi ngắn nhất trong chu trình
	static void DFSFindMin(int start, int end) {
		// minMayBanDa = 0;
		int k = mangMayBanDa[end] + mangMayBanDa[parents[end]];
		if (minMayBanDa > k) {
			startVong = end;
			endVong = parents[end];
			minMayBanDa = k;
		}
		if (  start == parents[end] ) { // da di qua het chu trinh 
			maTranKe[startVong][endVong] = 0; // cat canh
			maTranKe[endVong][startVong] = 0;
			
			result += minMayBanDa;
			for (int i = 0; i < m; i++) {
				visit[i] = 0;
				parents[i] = -1;
			}
			return;
		} else
			DFSFindMin(start, parents[end]);
	}

	// Tìm chu trình
	static void DFSCycle(int dinh) {
		visit[dinh] = 1;
		for (int i = 0; i < m; i++) {
			if (maTranKe[dinh][i] == 1) {
				if (visit[i] == 0) {
					if (kqvong == 0) {
						parents[i] = dinh;
						DFSCycle(i);
					}
				} else if (parents[dinh] != i) {
					startVong = i;
					endVong = dinh;
					minMayBanDa = mangMayBanDa[i] + mangMayBanDa[dinh];

					DFSFindMin(startVong, endVong);
					kqvong = 1;
					return;
				}
			}
		}
	}

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream(
				"src/tan_cong_thanh_tri/input_tan_cong_thanh_tri.txt"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			reset();
			m = scanner.nextInt(); // so thanh tri = so node
			start = System.currentTimeMillis();
			for (int i = 0; i < m; i++) {
				a = scanner.nextInt(); // so hieu
				b = scanner.nextInt(); // so may ban da
				c = scanner.nextInt(); // so luong thanh luy lien ket
				mangMayBanDa[a] = b;
				for (int j = 1; j <= c; j++) {
					d = scanner.nextInt();
					maTranKe[a][d] = 1;
					maTranKe[d][a] = 1;
				}
			}
			// print();
			// matranke
//			System.out.println("Case #" + tc);
//
//			for (int i = 0; i < m; i++) {
//				for (int j = 0; j < m; j++) {
//					System.out.print(maTranKe[i][j] + " ");
//				}
//				System.out.println();
//			}
//			// mang Trong So
//			System.out.println();
//			for (int i = 0; i < m; i++) {
//				System.out.print(mangMayBanDa[i] + " ");
//			}
//			System.out.println();
					
			minMayBanDa = 0;
			for (int i = 0; i < m; i++) {
				do {
					kqvong = 0; // break  
					for (int j = 0; j < m; j++) {
						visit[j] = 0;
						parents[j] = -1;
					}
					DFSCycle(i);
				} while (kqvong == 1);
			}
			
//			System.out.println();
//
//			// mang parent
//			for (int i = 0; i < m; i++) {
//				System.out.print(parents[i] + " ");
//			}
//			System.out.println();
//			// mang visited
//			for (int i = 0; i < m; i++) {
//				System.out.print(visit[i] + " ");
//			}
//			System.out.println();
			
			System.out.println(result);
		}
		scanner.close();
		//end = System.currentTimeMillis();
		//System.out.println(end - start + " ms");
	}
}
///////////////
31 turn over game
package co_vay;

import java.util.Scanner;

public class Solution2_co_vay {

	static int N = 4, cnt, min;
	static long start, end;
	static char x;
	static boolean map[][] = new boolean[4][4];

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);

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

			for (int i = 0; i < N; i++) {
				String inp = sc.next();
				for (int j = 0; j < N; j++) {
					x = inp.charAt(j);
					if (x == 'b') {
						map[i][j] = true;
					} else {
						map[i][j] = false;
					}
				}
			}

			min = 100000;

			BT(0, 0);
			System.out.println("Case #" + tc);

			if (min == 100000) {
				System.out.println("impossible");
			} else {
				System.out.println(min);
			}
		}
		sc.close();
	}

	private static void BT(int k, int cnt) {
		if (cnt >= min) { // chi dung voi cac bai tim min
			return;
		}
		if (check()) {
			min = min > cnt ? cnt : min;
			return;
		}

		if (k == N * N) {

			return;
		}

		int r = k / N;
		int c = k % N;

		for (int i = 0; i < 2; i++) {
			if (i == 1) {

				map[r][c] = !map[r][c];
				if (r - 1 >= 0) {
					map[r - 1][c] = !map[r - 1][c];
				}
				if (r + 1 < N) {
					map[r + 1][c] = !map[r + 1][c];
				}
				if (c - 1 >= 0) {
					map[r][c - 1] = !map[r][c - 1];
				}
				if (c + 1 < N) {
					map[r][c + 1] = !map[r][c + 1];
				}

				BT(k + 1, cnt + 1);

				map[r][c] = !map[r][c];
				if (r - 1 >= 0) {
					map[r - 1][c] = !map[r - 1][c];
				}
				if (r + 1 < N) {
					map[r + 1][c] = !map[r + 1][c];
				}
				if (c - 1 >= 0) {
					map[r][c - 1] = !map[r][c - 1];
				}
				if (c + 1 < N) {
					map[r][c + 1] = !map[r][c + 1];
				}
			} else {
				BT(k + 1, cnt);
			}
		}

	}

	private static boolean check() {
		boolean a = map[0][0];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != a) {
					return false;
				}
			}
		}
		return true;
	}
}
//////
32 harry 
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include<iostream>
using namespace std;
 
int T, N, M, K;
int sx, sy, ex, ey;
char forest[101][101];
int flag, ans;
int visited[101][101];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
void input(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        cin >> forest[i];
    }
    cin >> K;
}
void init(){
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            visited[i][j] = 0;
        }
    }
    ans = 0xFFFFFFF;
    flag = 0;
}
int solve(int x, int y, int cost){
    if (x == ex && y == ey){
        if (cost == K){
            flag = 1;
            return 1;
        }
        else{
            return 0;
        }
    }
    if (cost > K)
        return 0;
    if (visited[x][y] == 0){
        visited[x][y] = 1;
        int f = 0;
        for (int i = 0; i < 4; i++){
            int rx = x + dx[i];
            int ry = y + dy[i];
            if (rx >= 0 && rx < N && ry >= 0 && ry < M && visited[rx][ry] == 0 && forest[rx][ry] != 'M')f++;
        }
        for (int i = 0; i < 4; i++){
            int rx = x + dx[i];
            int ry = y + dy[i];
            if (rx >= 0 && rx < N && ry >= 0 && ry < M && visited[rx][ry] == 0 && forest[rx][ry] != 'M' && f >= 2){
                if (solve(rx, ry, cost + 1))return 1;
            }
            else if (rx >= 0 && rx < N && ry >= 0 && ry < M && visited[rx][ry] == 0 && forest[rx][ry] != 'M' && f == 1){
                if (solve(rx, ry, cost))return 1;
            }
        }
        visited[x][y] = 0;
    }
    return 0;
}
 
int main(){
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int tc = 1; tc <= T; tc++){
        input();
        init();
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                if (forest[i][j] == 'H'){
                    sx = i;
                    sy = j;
                }
                if (forest[i][j] == 'W'){
                    ex = i;
                    ey = j;
                }
            }
        }
        solve(sx, sy, 0);
        if (flag){
            cout << "#" << tc << ": Harry can leave\n";
        }
        else{
            cout << "#" << tc << ": Harry is stuck forever\n";
        }
    }
    return 0;
}
//////////////
33 paul trip 
#include <stdio.h>
int tc, n, m, edge[36][36], max, start, q[40], path[40], lp, rear;
struct location{
    char type;
    int time, v;
    bool visit;
}loc[36];
 
void dfs(int cur, int v, int day, int r){
    if (day == m){
        if (max < v){
            max = v;
            for (int i = 0; i<rear; ++i)path[i] = q[i];
            lp = rear;
        }
        return;
    }
    for (int i = 1; i <= n; ++i){
        if (loc[i].visit || edge[cur][i]>r)continue;
        q[rear++] = i;
        if (loc[i].type == 'A'&&day == m - 1)
            dfs(i, v, m, r);
        else if (loc[i].type == 'H'&&day != m - 1)
            dfs(i, v, day + 1, 540);
        else if (loc[i].type == 'P'&&edge[cur][i] + loc[i].time < r){
            loc[i].visit = 1;
            dfs(i, v + loc[i].v, day, r - edge[cur][i] - loc[i].time);
            loc[i].visit = 0;
        }
        --rear;
    }
}
 
int main(){
    scanf("%d", &tc);
    for (int t = 1; t <= tc; ++t){
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j){
            scanf("%d", &edge[i][j]);
            edge[j][i] = edge[i][j];
        }
        lp = rear = max = 0;
        for (int i = 1; i <= n; ++i){
            scanf(" %c", &loc[i].type);
            if (loc[i].type == 'A')start = i;
            if (loc[i].type == 'P')scanf("%d%d", &loc[i].time, &loc[i].v);
        }
        dfs(start, 0, 0, 540);
        printf("#%d %d ", t, max);
        for (int i = 0; i < lp; ++i)printf("%d ", path[i]);
        printf("\n");
    }
    return 0;
}
/////////////////
34 qua cau
package qua_cau;

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

class Queue {
	static int maxQ = 1000001;
	int data[] = new int[maxQ];
	int rear, front;

	public Queue() {
		front = rear = -1;
	}

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

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

	void enQ(int v) {
		data[++rear] = v;
	}

	int deQ() {
		return data[++front];
	}
}

public class Solution_qua_cau {
	static int N, cnt, max;
	static int map[][];
	static int[] dx = { -1, -1, -1 };
	static int[] dy = { -1, 0, 1 };

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

		System.setIn(new FileInputStream("w4wed/qua_cau/qua_cau.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 + 1][5];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 5; j++) {
					map[i][j] = sc.nextInt();
				}
			}

			// cnt = 0;
			max = -1;
			// checkLoThung() ;

			backtrack(N, 2, 1, 0);
			System.out.println("#" + tc + " " + max);

		}
	}

	private static void checkLoThung() {
		// neu tat ca la 2
		boolean check;
		for (int i = 0; i < N; i++) {
			check = true; // tat ca la 2
			for (int j = 0; j < 5; j++) {
				if (map[i][j] != 2) {
					check = false;
				}
			}
			if (check) {
				cnt++; // dem xem co bn hang tat ca la 2
			}
		}

	}

	private static void backtrack(int r, int c, int soVan , int coin) {
		if (r == 0) {
			// max = max > coin ? max : coin ;
			max = Math.max(max, coin);
		}

		for (int k = 0; k < 3; k++) {
			int newr = r + dx[k];
			int newc = c + dy[k];

			if (newr >= 0 && newr < N && newc >= 0 && newc < 5) {
				// xu ly lo thung
				if (map[newr][newc] == 2 && soVan >= 1) {
					backtrack(newr, newc, soVan - 1, coin);
				}
				if (map[newr][newc] == 1) {
					backtrack(newr, newc, soVan, coin + 1);
				}
				if (map[newr][newc] == 0) {
					backtrack(newr, newc, soVan, coin);
				}
			}
		}

	}
}
//////////////
35 crayzy king

package crayzy_king;

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

class Queue {
	static final int maxq = 1000001;
	int data[] = new int[maxq];
	int front, rear;

	Queue() {
		front = rear = -1;
	}

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

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

	void enQ(int v) {
		data[++rear] = v;
	}

	int deQ() {
		return data[++front];
	}
}

public class Solution_crayzy_king {
	static boolean dead;
	static int n, m;
	static int sx, sy, ex, ey;
	static int map[][];
	static int visitKing[][];
	static int dxZebra[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
	static int dyZebra[] = { -2, -1, 1, 2, 2, 1, -1, -2 };

	static int dxKing[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
	static int dyKing[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static Queue qx = new Queue();
	static Queue qy = new Queue();

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

		System.setIn(new FileInputStream(
				"w4wed/crayzy_king/input_crayzy_king.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];
			visitKing = new int[n][m];
			for (int i = 0; i < n; i++) {
				String inp = sc.next();
				for (int j = 0; j < m; j++) {
					map[i][j] = inp.charAt(j);
					if (map[i][j] == 'A') {
						sx = i;
						sy = j;
					}
					if (map[i][j] == 'B') {
						ex = i;
						ey = j;
					}
				}
			}

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (map[i][j] == 'Z') {
						control_Zebra(i, j);
					}
				}
			}
			BFS_king(sx, sy);

			if (visitKing[ex][ey] == 0) {
				System.out.println(-1);
			} else {
				System.out.println(visitKing[ex][ey] - 1);
			}

		}
	}

	private static void BFS_king(int i, int j) {
		qx.reset();
		qy.reset();
		qx.enQ(sx);
		qy.enQ(sy);

		visitKing[i][j] = 1;
		while (!qx.isE()) {
			int r = qx.deQ();
			int c = qy.deQ();
			for (int k = 0; k < 8; k++) {
				int newr = r + dxKing[k];
				int newc = c + dyKing[k];
				if (newr < 0 || newr >= n || newc < 0 || newc >= m) {
					continue;
				}
				if (visitKing[newr][newc] == 0) {
					if (map[newr][newc] == 'B' || map[newr][newc] == '.') {
						visitKing[newr][newc] = visitKing[r][c] + 1;
						qx.enQ(newr);
						qy.enQ(newc);
					}

				}
			}
		}
	}

	static void control_Zebra(int i, int j) {
		for (int u = 0; u < 8; u++) {
			int x = i + dxZebra[u];
			int y = j + dyZebra[u];
			if (x >= 0 && x < n && y >= 0 && y < m) {
				if (map[x][y] == '.') {
					map[x][y] = 'X';
				}
			}
		}
	}
}
/////////////////////
37 hobit
#include <stdio.h>
 
#define max_len 1005
 
bool visited[max_len][max_len];
int maze[max_len][max_len];
 
int max;
int N, M;
int test_case;
 
int is_valid(int x1, int y1, int x2, int y2)
{
    if (x2 >= 1 && x2 <= N && y2 >= 1 && y2 <= M && visited[x2][y2] == false && maze[x1][y1] != maze[x2][y2]) return 1;
    else return 0;
}
 
void travel(int x, int y, int steps)
{
    if (steps > max) return;
    if (x == N && y == M)
    {
        if (steps <= max) max = steps;
        return;
    }
    visited[x][y] = true;
    if (is_valid(x, y, x, y + 1)) travel(x, y + 1, steps + 1);
    if (is_valid(x, y, x + 1, y)) travel(x + 1, y, steps + 1);
    if (is_valid(x, y, x, y - 1)) travel(x, y - 1, steps + 1);
    if (is_valid(x, y, x - 1, y)) travel(x - 1, y, steps + 1);
    if (test_case != 10) visited[x][y] = false;
}
 
int main(void)
{
    //int test_case;
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d %d", &N, &M);
        for (register int i = 1; i <= N; i++)
        {
            for (register int j = 1; j <= M; j++)
            {
                scanf("%d", &maze[i][j]);
                visited[i][j] = false;
            }
        }
        int steps = 1;
        max = 99999;
        travel(1, 1, steps);
        if (max == 0 || max == 99999) max = -1;
        printf("#%d %d\n", test_case, max);
    }
    return 0;
}
/////
38 he thong dien
import java.util.Scanner;

public class Solution {
	
	static class Queue{
		static int maxq = 100001 ;
		int data[] = new int[maxq] ;
		int front, rear ;
		
		Queue(){
			front = rear = -1 ;
		}
		void reset(){
			front = rear = -1;
		}
		boolean isEmpty(){
			return front == rear ;
		}
		void enq(int v){
			data[++rear] = v ;
		}
		int deq(){
			return data[++front] ;
		}
		int peek(){
			return data[front+1] ;
		}
	}
	
	static int n , m , h ;
	static int u, v ;
	static int idMayPhatdien[] ;
	static int maTranKe[][] ;
	static int visit[] ;
	static int resDoManhYeu[] ;
	static Queue q = new Queue() ;
	static Queue qx = new Queue() ;
	static Queue qy = new Queue() ;
	
	public static void main(String[] args) throws Exception {
		
		Scanner sc = new Scanner(System.in) ;
		int T = sc.nextInt() ;
		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt() ; // so dao
			m = sc.nextInt() ; // so dao co tram phat dien
			h = sc.nextInt() ; // so ket noi 2 chieu
			
			idMayPhatdien = new int[m] ;
			for (int i = 0; i < m; i++) {
				idMayPhatdien[i] = sc.nextInt();
			}
			
			maTranKe = new int[n][n] ;
			
			for (int i = 0; i < h; i++) {
					u = sc.nextInt() ;
					v = sc.nextInt() ;
					maTranKe[u][v] = 1 ;
					maTranKe[v][u] = 1 ;
			}


			resDoManhYeu = new int[n+1] ;
			for (int i = 0; i < resDoManhYeu.length; i++) {
				resDoManhYeu[i] = Integer.MAX_VALUE;
			}

			BFS();
			
			int max = -1, ans = 0;
			for (int i = 0; i < n; i++) {
				if( resDoManhYeu[i] > max){
					max = resDoManhYeu[i] ;
					ans = i ;
				}
			}
			System.out.println(ans);
			
		}
	}
	private static void BFS() {
		q.reset();
		for(int i=0; i<m; i++){
			q.enq(idMayPhatdien[i]);
			resDoManhYeu[idMayPhatdien[i]] = 0;
		}
		//visit[u] = 1;
		while( !q.isEmpty()){
			int curU = q.deq();
			//duyet theo tung dinh cua dao
			for (int k = 0; k < n; k++) {
				if( resDoManhYeu[k] == Integer.MAX_VALUE && maTranKe[curU][k] == 1){
					resDoManhYeu[k] = resDoManhYeu[curU] + 1; 
					q.enq(k); 
				}
			}
		}
		
	}
}
/////////////////
39 helping mario
#include <iostream>
 
using namespace std;
int m, ans;
int a[101][101];
bool vis[101][101];
bool flag1, flag2, isPath;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
 
void resetVis() {
    for (int i = 1; i <= m; i++) 
        for (int j = 1; j <= m; j++) 
            vis[i][j] = false;      
}
 
void fun(int i, int j) {
    if (i == 1) {
        flag1 = true;
    }
    else if (i == m) {
        flag2 = true;
    }
    vis[i][j] = true;
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k];
        int y = j + dy[k];
        if (x > 0 && x <= m && y > 0 && y <= m && a[x][y] == 1 && !vis[x][y])
            fun(x, y);
    }
}
 
int main()
{
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        cin >> m;
        for (int i = 0; i <= m; i++) 
            for (int j = 0; j <= m; j++)
                a[i][j] = 0;  //fire            
        ans = 0;
        flag1 = false;
        flag2 = false;
        for (int i = 1; i <= m * m; i++) {
            int x, y;
            cin >> x >> y;
            a[x][y] = 1;  //sand
            if (!flag1 || !flag2) {
                flag1 = false;
                flag2 = false;
                resetVis();
                fun(x, y);
                if (flag1 && flag2) {
                    ans = i;
                }
            }
        }
        cout << "#" << test_case << " " << ans << "\n";
    }
    return 0;
}
///////////////
40 brave army
#include<iostream>
int T, M, N, X, Y;
int mang[7][7], visit[7][7];
int dX[4] = {1, -1, 0, 0};
int dY[4] = {0, 0, 1, -1};
int ans = 0;
 
void back(int x, int y, int tmpQuan, int count){
    if(ans < count){
        ans = count;    
    }
    for (int k = 0; k < 4; k++)
    {
        int a = dX[k] + x;
        int b = dY[k] + y;
        if(a > 0 && a <= M && b > 0 && b <= N && mang[a][b] != 0 && visit[a][b] == 0){
            visit[a][b] = 1;
            if(mang[a][b] *2 <= tmpQuan){
                back(a, b, tmpQuan + mang[a][b], count +1);
            }
            else if(mang[a][b] <= tmpQuan){
                back(a, b, tmpQuan - mang[a][b], count +1);
            }
            visit[a][b] = 0;
        }
    }
}
 
using namespace std;
int main(){
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin>>T;
    for (int tc = 0; tc < T; tc++)
    {
        cin>>M>>N>>X>>Y;
        for (int i = 1; i <= M; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                cin>>mang[i][j];
                visit[i][j] = 0;
            }
        }
        ans = 0;
        visit[X][Y] = 1;
        back(X, Y, mang[X][Y], 1);
        cout<<"#"<<tc + 1<<" "<<ans<<endl;
    }
	return 0;
}
////////////////////
41 lan birthday
#include <stdio.h>
int n, m, X;
int u, v, d;
int map1[1001][1001], map2[1001][1001];
int least1[1001], least2[1001], visited[1001];
 
void init(){
    for (int i = 0; i <=1001; i++){
        least1[i] = 0x7fffffff;
        least2[i] = 0x7fffffff;
    }
    for (int i = 0; i <=1001; i++)
        for (int j = 0; j < 1001; j++){
            map1[i][j] = 0x7fffffff;
            map2[i][j] = 0x7fffffff;
        }
}
 
void Dijkstra(int temp[], int graph[1001][1001]){
    for (int i = 1; i <= n; i++){
        visited[i] = 0;
        temp[i] = graph[X][i];
    }
    temp[X] = 0;
    for (int i = 1; i <= n; i++){
        int min = 0x7fffffff;
        int a = 1;
        for (int k = 1; k <= n; k++){
            if (visited[k] == 0 && temp[k] < min){
                min = temp[k];
                a = k;
            }
        }
        visited[a] = 1;
        for (int j = 1; j <= n; j++){
            if (visited[j] == 0 && graph[a][j] < 0x7fffffff){
                int b = graph[a][j] + temp[a];
                if (b < temp[j])
                    temp[j] = b;
            }
        }
    }
}
 
int main(){
    int tc, T;
    //freopen("system_input.txt", "r", stdin);
    scanf("%d", &T);
    for (tc = 1; tc <= T; tc++){
        init();
        scanf("%d %d %d", &n, &m, &X);
        for (int i = 0; i < m; i++){
            scanf("%d %d %d", &u, &v, &d);
            map2[v][u] = d;
            map1[u][v] = d;
        }
        Dijkstra(least1, map1);
        Dijkstra(least2, map2);
        int ret = 0;
        for (int i = 1; i <= n; i++){
            if (least1[i] + least2[i] > ret && least1[i]<0x7fffffff && least2[i]<0x7fffffff){
                ret = least1[i] + least2[i];
            }
        }
        printf("#%d %d\n", tc, ret);
    }
    return 0;
}
//////////////
42 hugo kim cuong
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

int N,M, x_start, y_start,data[17][17],dx[]={0,0,1,-1}, dy[]={1,-1,0,0}, num_ho, num_chay,map[17][17], num_thoat,visit[17][17],front,rear,ans;
struct Pos{
	int row,col;
}chay[40], ho[40], thoat[40], queue[301];
void en(int r,int c){
	rear++;
	queue[rear].row = r;
	queue[rear].col = c;
}
Pos de(){
	front++;
	return queue[front];
}
void burn(){
	
	while(front != rear){
		Pos p = de();
		for (int k = 0; k < 4; k++)
		{
			int x = p.row+dx[k];
			int y = p.col+dy[k];
			if(x>=0 && y>=0 && x<N && y<M && map[x][y]==0 && map[x][y] != 9999) {
				map[x][y] = map[p.row][p.col] + 1;
				en(x,y);
			}
		}
	}
}

bool check_exit(int x,int y){
	for (int i = 0; i < num_thoat; i++)
	{
		if(thoat[i].row == x && thoat[i].col == y) return true;
	}
	return false;
}

void Try(int x,int y,int count){
	if(map[x][y] != 9999  && map[x][y] != 0 && visit[x][y] >= map[x][y]) return;

	if(check_exit(x,y)){
		if(count > ans) ans = count;
	}

	for (int i = 0; i < 4; i++)
	{
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(xx>=0 && yy>=0 && xx<N && yy<M && visit[xx][yy]==0){
			if(map[xx][yy] == 9999){
				visit[xx][yy] = visit[x][y]+2;
			}else{
				visit[xx][yy] = visit[x][y]+1;
			}
			Try(xx,yy, count+data[xx][yy]);
			
			visit[xx][yy] = 0;
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	int Answer;
	
	ios::sync_with_stdio(false);

	freopen("input.txt", "r", stdin);
	cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
		Answer = ans = 0;
		front = rear = -1;
		for (int i = 0; i < 17; i++)
		for (int j = 0; j < 17; j++){
			map[i][j] = visit[i][j] = 0;
		}
		//INPUT
		int a,b;
		cin>>N>>M>>x_start>>y_start;
		cin>>num_chay;
		x_start--; y_start--;
		for (int i = 0; i < num_chay; i++)
		{
			
			cin>>a>>b;
			chay[i].row = a-1;
			chay[i].col = b-1;
			map[a-1][b-1] = 1;
			en(chay[i].row,chay[i].col);
		}
		cin>>num_ho;
		for (int i = 0; i < num_ho; i++)
		{
			cin>>a>>b;
			ho[i].row = a-1;
			ho[i].col = b-1;
			map[a-1][b-1] = 9999; 
		}
		cin>>num_thoat;
		for (int i = 0; i < num_thoat; i++)
		{
			cin>>a>>b;
			thoat[i].row = a-1;
			thoat[i].col = b-1;
		}
		for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin>>data[i][j];

		//PREPROCESS
		burn();
		
		visit[x_start][y_start] = 1;
		//PROCESS
		Try(x_start,y_start,data[x_start][y_start]);

		// Print the answer to standard output(screen).
		if(ans !=0)
			cout << "Case #" << test_case << endl << ans << endl;
		else
			cout << "Case #" << test_case << endl << -1  << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}
43 lazer
#include<iostream>
#define MAXX(a,b)a>b?a:b
using namespace std;
int shoot(int a[][20],int n,int m)
{
    int count[n], zero[n],ans=-1;
    for(int i=0;i<n;i++)
    {   int k=0;
        for(int j=0;j<n;j++)
          { 
			if(a[i][j]==0)
              k++;
          }
          zero[i]=k;
    }
   
    for(int i=0;i<n;i++)
    {  count[i]=0;
        for(int j=0;j<n;j++)
        { int k=0;
            while(k!=n)
            {
                if(a[i][k]!=a[j][k]) break; 
                else k++;
            }
            if(k==n) count[i]++;
        } 
     
    }
    for(int i=0;i<n;i++)
    {
        if((m-zero[i])%2==0 and m>=zero[i])
            ans=MAXX(ans,count[i]);
        else continue;
    }
    return ans;
    }
int main(int argc, char** argv)
{
	int test_case;
	int T;


	//freopen("input.txt", "r", stdin);
	cin>>T;

	/*
	   Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
  int n,m;
		
     cin>>n>>m;
        int a[n][20];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>a[i][j];
        cout<<"#"<<test_case<<" "<<shoot(a,n,m)<<endl;

	}
	return 0;//Your program should return 0 on normal termination.
}

///////////////
44 diamond
package diamond;


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

public class Solution_dia {
	static int N ; 
	static int arr[][];
	static int visit[];
	static int ret ;

static void DFS(int i, int start){
	visit[i] = 1;
	//int ret = 0;
	if(ret == 1){
		return;
	}
	int x = arr[i][0];
	for(int j = 1; j <= x ;j++ ){
		if(visit[arr[i][j]] == 0){
			DFS(arr[i][j], start);
		}
		else {
			if(arr[i][j] != start) 
			{   
				ret = 1;
				return;
			}
		}	
	}
}
				
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/diamond/input_diamond.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc ++){
			N = scanner.nextInt();
			arr = new int[N+1][N+1];
			
			for(int i = 1; i< N+1 ; i++){
				//visit[i] = 0;
				int x = scanner.nextInt();
				arr[i][0]= x;
				for(int j = 1; j<= x ; j++){
					arr[i][j] = scanner.nextInt();
				}
			}
			String check = "No";
			for(int i = 1; i<= N ; i++){
				visit = new int[N+1];
				ret = 0;
				DFS(i, i);
				if(ret== 1)
				{
					check ="Yes";
					break;
				}

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

}
Leave a Comment