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...