Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
20 kB
26
Indexable
Never
package Laughing_Bomb;

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

public class laughing_bomb {
	static int m, n, bx, by, ans;
	static int [][] map, visit;
	static int [] dx = {1, 0, -1, 0};
	static int [] dy = {0, 1, 0, -1};
	static int MAX_SIZE = 100000;
	static int [][] queue = new int [MAX_SIZE][2];
	static int rear, front;
	
	static void push (int x, int y) {
		if (rear == MAX_SIZE - 1) rear = -1;
		rear++;
		queue[rear][0] = x;
		queue[rear][1] = y;
	}
	static void pop() {
		if (front == MAX_SIZE - 1) front = -1;
		front++;
	}
	static int tx() {
		return queue[front][0];
	}
	static int ty() {
		return queue[front][1];
	}
	static boolean isEmpty() {
		return rear == front;
	}
	static void bfs (int x, int y) {
		rear = front = -1;
		push(x, y);
		visit[x][y] = 1;
		while (!isEmpty()) {
			pop();
			int a = tx();
			int b = ty();
			for (int i = 0; i < 4; i++) {
				int x1 = a + dx[i];
				int y1 = b + dy[i];
				if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= m || map[x1][y1] == 0 || visit[x1][y1] != 0) continue;
				visit[x1][y1] = visit[a][b] + 1;
				ans = visit[x1][y1];
				push(x1, y1);
			}
		}
	}
	
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src//Laughing_Bomb//bomb.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			m = sc.nextInt();
			n = sc.nextInt();
			map = new int [n][m];
			visit = new int [n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			by = sc.nextInt() - 1;
			bx = sc.nextInt() - 1;
			bfs(bx, by);
			if (map[bx][by] == 0) ans = ans - 1;
			System.out.println(ans);
		}
	}
}
-----------------------------------------------
package Sky_Tour;

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

public class sky_tour {
	static int n, e, ans;
	static int [][] map;
	static int [] dx = {2, 1, 0, -1, -2};
	static int [] dy = {1, 1, 1, 1, 1};
	static void Try (int x, int y, int ene, int score) {
		if (y == n) {
			if (ans < score) ans = score;
			return;
		}
		for (int i = 0; i < 5; i++) {
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if (x1 < 0 || x1 >= 3 || y1 < 0 || y1 > n) continue;
			if ((i == 0 || i == 3) && ene >= 2) {
				Try(x1, y1, ene - 2, score + map[x1][y1]);
			} else if (i == 1 && ene >= 1) {
				Try(x1, y1, ene - 1, score + map[x1][y1]);
			} else if (i == 4 && ene >= 4) {
				Try(x1, y1, ene - 4, score + map[x1][y1]);
			} else if (i == 2){
				Try(x1, y1, ene, score + map[x1][y1]);
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//Sky_Tour//sky_tour.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			e = sc.nextInt();
			n = sc.nextInt();
			map = new int [3][n+1];
			for (int i = 0; i < 3; i++) {
				for (int j = 1; j <= n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			ans = 0;
			Try(1, 0, e, 0);
			System.out.println("#" + test_case + " " + ans);
		}
	}
}
------------------------------------------
package Chi_Ong_nau;
import java.util.Scanner;
public class Solution {
	
	static int row, col;
	static long ans;
	static int[][] map;
	static int[][] dl = {{-1, 0, 1, 1, 1, 0}, {0, 1, 1, 0, -1, -1}};
	static int[][] dc = {{-1, -1, 0, 1, 0, -1}, {0, 1, 1, 0, -1, -1}};
	static boolean[][] visit;
	
	private static void DFS(int x, int y, int sum, int cnt){
		if(cnt == 4){
			ans = sum > ans ? sum : ans;
			return;
		}
			
		int dx, dy;
		for(int i = 0; i < 6; i++){
			if(y % 2 == 0){
				dx = x + dc[0][i]; dy = y + dc[1][i];
			}
			else{
				dx = x + dl[0][i]; dy = y + dl[1][i];
			}
			
			if(dx >= 0 && dy >= 0 && dx < row && dy < col && !visit[dx][dy]){
				visit[dx][dy] = true;
				DFS(dx, dy, sum + map[dx][dy], cnt + 1);
				visit[dx][dy] = false;
			}
		}
	}
	
	public static void DFS2(int x, int y){
		int suml = map[x][y], sumc = map[x][y], cntl = 1, cntc = 1;
		int dx, dy;
		for(int i = 0; i < 6; i++){
			if(i % 2 == 0){
				dx = x + dc[0][i]; dy = y + dc[1][i];
				if(dx >= 0 && dy >= 0 && dx < row && dy < col){
					cntc++;
					sumc += map[dx][dy];
				}
			}
			else{
				dx = x + dl[0][i]; dy = y + dl[1][i];
				if(dx >= 0 && dy >= 0 && dx < row && dy < col){
					cntl++;
					suml += map[dx][dy];
				}
			}
		}
		
		if(cntc == 4) ans = sumc > ans ? sumc : ans;
		if(cntl == 4) ans = suml > ans ? suml : ans;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			col = sc.nextInt(); row = sc.nextInt();
			map = new int[row][col];
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					map[i][j] = sc.nextInt();
				}
			}

			visit = new boolean[row][col];
			ans = 0;
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					visit[i][j] = true;
					DFS(i, j, map[i][j], 1);
					visit[i][j] = false;
					DFS2(i, j);
				}
			}
			
			ans = ans * ans;
			System.out.println("Case #" + tc);
			System.out.println(ans);
		}
	}
}
-----------------------------------------------
package Cover_Rectangle_Dominos;

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

public class cover_rectangle_dominos {
	static int m = 7;
	static int n = 8;
	static int [][] map = new int [m][n];
	static int [][] visit_domino, visit;
	static int ans;
	static int [][] d = {{0, 1}, {1, 0}};
	
	static void Try(int k) {
		if (k == 56) {
			ans++;
			return;
		}
		int x = k / 8;
		int y = k % 8;
		if (visit[x][y] == 0) {
			for (int i = 0; i < 2; i++) {
				int x1 = x + d[i][0];
				int y1 = y + d[i][1];
				if (x1 < m && y1 < n && visit[x1][y1] == 0 && visit_domino[map[x][y]][map[x1][y1]] == 0) {
					visit[x1][y1] = visit[x][y] = 1;
					visit_domino[map[x][y]][map[x1][y1]] = visit_domino[map[x1][y1]][map[x][y]] = 1;
					Try(k+1);
					visit[x1][y1] = visit[x][y] = 0;
					visit_domino[map[x][y]][map[x1][y1]] = visit_domino[map[x1][y1]][map[x][y]] = 0;
				}
			}
		} else {
			Try(k+1);
		}
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//Cover_Rectangle_Dominos//domino.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			visit = new int [m][n];
			visit_domino = new int [m][m];
			ans = 0;
			Try(0);
			System.out.println("#" + test_case + " " + ans);
		}
	}
}
------------------------------------------------
package Dao_Cot;

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

public class dao_Cot {
	static int m, n, k, ans;
	static int [][] map;
	static int find_row(int x) {
		int ans = 0;
		int count = 0;
		for (int i = 0; i < n; i++) {
			if (map[x][i] == 0) {
				count++;
			}
		}
		if (k >= count && (k - count) % 2 == 0) {
			ans = 1;
			for (int i = 0; i < m; i++) {
				boolean check = true;
				if (i != x) {
					for (int j = 0; j < n; j++) {
						if (map[x][j] != map[i][j]) {
							check = false;
							break;
						}
					}
					if (check) {
						ans++;
					}
				}
			}
		}
		return ans;
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//Dao_Cot//dao_cot.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			m = sc.nextInt();
			n = sc.nextInt();
			k = sc.nextInt();
			map = new int [m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			ans = 0;
			for (int i = 0; i < m; i++) {
				int num = find_row(i);
				if (ans < num) ans = num;
			}
			System.out.println("Case #" + test_case + " " + ans);
		}
	}
}
---------------------------------------------------
package MarioClimd;

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

public class marioClimd {
	static int MAX_SIZE = 100000;
	static int [][] queue = new int [MAX_SIZE][2];
	static int rear, front;
	static void push (int x, int y) {
		if (rear == MAX_SIZE - 1) rear = -1;
		rear++;
		queue[rear][0] = x;
		queue[rear][1] = y;
	}
	static void pop() {
		if (front == MAX_SIZE - 1) front = -1;
		front++;
	}
	static boolean isEmpty() {
		return rear == front;
	}
	static int [] dx = {1, 0, -1, 0};
	static int [] dy = {0, 1, 0, -1};
	
	static void reset() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visit[i][j] = 0;
			}
		}
	}
	
	static boolean bfs(int x, int y, int step) {
		rear = front = -1;
		push(x, y);
		visit[x][y] = 1;
		while (!isEmpty()){
			pop();
			int a = queue[front][0];
			int b = queue[front][1];
			for (int j = 1; j <= step; j++) {
				for (int i = 0; i < 4; i++) {
					int x1 = a + j*dx[i];
					int y1 = b + dy[i];
					if (x1 >= 0 && y1 >= 0 && x1 < n && y1 < m && visit[x1][y1] == 0 && map[x1][y1] != 0) {
						if (x1 == ex && y1 == ey) return true;
						visit[x1][y1] = 1;
						push(x1, y1);
					}
				}
			}
		}
		return false;
	}

	static int n, m, sx, sy, ex, ey;
	static int [][] map, visit;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//MarioClimd//mario.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			rear = front = -1;
			n = sc.nextInt();
			m = sc.nextInt();
			map = new int [n][m];
			visit = new int [n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 2) {
						sx = i;
						sy = j;
					} 
					if (map[i][j] == 3) {
						ex = i;
						ey = j;
					}
				}
			}
			int step = 1;
			while (true) {
				reset();
				if (bfs(sx, sy, step)) {
					break;
				}
				step++;
			}
			System.out.println("Case #" + test_case);
			System.out.println(step);
		}
	}
}
-----------------------------------------------------
package Path_Find;

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

public class path_find {
	static int n;
	static int [][] map, visit;
	static int [] dx = {1, 0, -1, 0};
	static int [] dy = {0, 1, 0, -1};
	static int [][] queue = new int [1000][2];
	static int rear, front;
	static boolean check;
	
	static void bfs (int x, int y) {
		rear = front = -1;
		rear++;
		queue[rear][0] = x;
		queue[rear][1] = y;
		visit[x][y] = 1;
		while (rear > front) {
			front++;
			int a = queue[front][0];
			int b = queue[front][1];
			for (int h = 0; h < 4; h++) {
				int x1 = a + map[a][b]*dx[h];
				int y1 = b + map[a][b]*dy[h];
				if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= n || visit[x1][y1] == 1 || map[x1][y1] == 0) continue;
				if (x1 == n-1 && y1 == n-1) {
					check = true;
					return;
				}
				rear++;
				queue[rear][0] = x1;
				queue[rear][1] = y1;
				visit[x1][y1] = 1;
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//Path_Find//path.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			map = new int [n][n];
			visit = new int [n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			check = false;
			bfs(0, 0);
			if (check) System.out.println("YES");
			else System.out.println("NO");
		}
	}
}
----------------------------------------------------
package Pick_Jewels;

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

public class pick_jewels {
		static int n, ans;
		static int [][] map, visit;
		static int [] dx = {1, 0, -1, 0};
		static int [] dy = {0, 1, 0, -1};
		static void Try(int x, int y, int jew) {
			if (visit[n-1][n-1] == 1) {
				if (ans < jew) ans = jew;
				return;
			}
			for (int h = 0; h < 4; h++) {
				int x1 = x + dx[h];
				int y1 = y + dy[h];
				if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= n || map[x1][y1] == 1 || visit[x1][y1] == 1) continue;
				if (map[x1][y1] == 2) {
					visit[x1][y1] = 1;
					Try(x1, y1, jew + 1);
					visit[x1][y1] = 0;
				} else {
					visit[x1][y1] = 1;
					Try(x1, y1, jew);
					visit[x1][y1] = 0;
				}
			}
		}
		
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//Pick_Jewels//jewel.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			map = new int [n][n];
			visit = new int [n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			ans = 0;
			visit[0][0] = 1;
			Try(0, 0, 0);
			System.out.println(ans);
		}
	}
}
--------------------------------------------
package The_Fellowship_of_The_Ring;

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

public class The_Ring {
	static int group;
	static int [] orc, cost;
	static int Ans;
	
	static void Try(int gate, int s1, int s2, int s3, int sumCost) {
		if (gate == group) {
			if (Ans > sumCost) Ans = sumCost;
			return;
		}
		if (Ans < sumCost) return;
		for (int i = 0; i < 3; i++) {
			if (i == 0) {
				Try(gate+1, s1, s2, s3, sumCost + cost[gate]);	// truong hop mua ve
			}  else if (i == 1) {		// truong hop mua linh
				Try(gate+1, s1 + orc[gate], s2, s3, sumCost + 2*cost[gate]);
			} else if (i == 2) {		// truong hop danh nhau
				if (s3 >= orc[gate]) Try (gate+1, 0, s1, 0, sumCost);
				else if (s3+s2 >= orc[gate]) Try(gate+1, 0, s1, s3+s2 - orc[gate], sumCost);
				else if (s3+s2+s1 >= orc[gate]) Try(gate+1, 0, s3+s2+s1 - orc[gate], 0, sumCost);
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//The_Fellowship_of_The_Ring//ring.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			group = sc.nextInt();		// so luong cong can di qua
			orc = new int[group];		// so luong orc o moi cong
			cost = new int[group];		// gia ve can de di vao cong
			for (int i = 0; i < group; i++) {
				orc[i] = sc.nextInt();
				cost[i] = sc.nextInt();
			}
			Ans = 100000;
			Try(0, 0, 0, 0, 0);
			System.out.println("#" + test_case + " " + Ans);
		}
	}
}
-------------------------------------------
package Trade_In_Phone_s6;

import java.io.FileInputStream;
import java.util.Scanner;
public class trade_in_phone_s6 {
	
	static int [][] queue = new int [10000][2];
	static int rear, front;
	static int [] dx = {1, 0, -1, 0};
	static int [] dy = {0, 1, 0, -1};
	
	static void find_Max_And_Fill () {
		int max = 0;
		int tmp = 0;
		for (int i = 5; i > 0; i--) {
			if (tmp < booth[i]) {
				tmp = booth[i];
				max = i;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visit[i][j] != 0 && temp[i][j] == 0) {
					temp[i][j] = max;
				}
			}
		}
	}
	
	static void reset() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				visit[i][j] = 0;
			}
		}
		for (int i = 0; i < 6; i++) {
			booth[i] = 0;
		}
	}
	
	static void bfs (int x, int y) {
		rear = front = -1;
		visit[x][y] = 1;
		rear++;
		queue[rear][0] = x;
		queue[rear][1] = y;
		while (rear > front) {
			front++;
			int a = queue[front][0];
			int b = queue[front][1];
			for (int h = 0; h < 4; h++) {
				int x1 = a + dx[h];
				int y1 = b + dy[h];
				if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= n || visit[x1][y1] == 1) continue;
				if (map[a][b] == 0 || map[a][b] == map[x1][y1]) {
					booth[map[x1][y1]]++;
					visit[x1][y1] = 1;
					rear++;
					queue[rear][0] = x1;
					queue[rear][1] = y1;
				}
			}
		}
		find_Max_And_Fill();
	}
	
	static void dfs(int x, int y) {
		visit[x][y] = 1;
		for (int i = 0; i < 4; i++) {
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= n || visit[x1][y1] == 1) continue;
			if (temp[x][y] == temp[x1][y1])	dfs(x1, y1);
		}
	}
	
	static int n, k;
	static int [][] map, temp, visit;
	static int [] booth;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//Trade_In_Phone_s6//phone.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			k = 0;
			n = sc.nextInt();
			map = new int [n][n];
			temp = new int [n][n];
			visit = new int [n][n];
			booth = new int [6];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++)  {
					temp[i][j] = map[i][j] = sc.nextInt();
				}
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (temp[i][j] == 0) {
						reset();
						bfs(i, j);
					}
				}
			}
			reset();
			int ans = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++)  {
					if (visit[i][j] == 0) {
						ans++;
						dfs(i, j);
					}
				}
			}
			System.out.println("Case #" + test_case);
			System.out.println(ans);
		}
	}
}
---------------------------------------------------
package Advertisement_Schedule;

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

public class advertisement_schedule {
	static int n, st_ads, ed_ads, ans;
	static int [] ads_len, point;
	static int [][] visitor, ads;
	
	static boolean is_set_ads(int x, int k) {
		for (int i = 0; i < 3; i++) {
			if (i != k) {
				if ((ads[0][i] > x && ads[0][i] < x + ads_len[k]) ||
						(ads[1][i] > x && ads[1][i] < x + ads_len[k]) 
						|| (x >= ads[0][i] && x + ads_len[k] <= ads[1][i])) return false;
			}
		}
		return true;
	}
	
	static void set_ads (int x, int k) {
		ads[0][k] = x;
		ads[1][k] = x + ads_len[k];
	}
	
	static void unset_ads (int x, int k) {
		ads[0][k] = 0;
		ads[1][k] = 0;
	}
	
	static int find_point (int x) {
		int tmp = 0;
		for (int i = 0; i < 3; i++) {
			if (visitor[x][0] <= ads[0][i] && visitor[x][1] >= ads[1][i]) {
				if (tmp < point[i]) tmp = point[i];
			}
		}
		
		return tmp;
	}
	
	static int find_all_point() {
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int tmp = find_point(i);
			sum += tmp;
		}
		return sum;
	}
	
	static void Try (int k) {
		if (k == 3) {
			int tmp = find_all_point();
			if (ans < tmp) ans = tmp;
			return;
		}
		for (int i = st_ads; i <= ed_ads; i++) {
			if (is_set_ads(i, k)) {
				set_ads(i, k);
				Try (k+1);
				unset_ads(i, k);
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src//Advertisement_Schedule//ads.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();			// so luong khach xem
			ads_len = new int [3];		// do dai quang cao
			point = new int [3];		// diem moi quang cao
			visitor = new int [n][2];	// thoi gian khach xem quang cao
			ads = new int [2][3];
			
			for (int i = 0; i < 3; i++) {
				ads_len[i] = sc.nextInt();
			}
			for (int i = 0; i < 3; i++) {
				point[i] = sc.nextInt();
			}
			st_ads = 1000000;
			ed_ads = 0;
			for (int i = 0; i < n; i++) {
				visitor[i][0] = sc.nextInt();		// start visitor'time
				int tmp = sc.nextInt();
				visitor[i][1] = visitor[i][0] + tmp;	// end visitor'time
				if (st_ads > visitor[i][0]) st_ads = visitor[i][0];
				if (ed_ads < visitor[i][1]) ed_ads = visitor[i][1];
 			}
			ans = 0;
			Try(0);
			System.out.println("Case #" + test_case);
			System.out.println(ans);
		}
	}
}