Untitled
unknown
plain_text
2 years ago
20 kB
28
Indexable
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); } } }
Editor is loading...