code v2
unknown
plain_text
2 years ago
19 kB
1
Indexable
hugo dao vang
package day16_2006;
//import java.io.FileInputStream;
//import java.io.FileNotFoundException;
import java.util.Scanner;
class MyQueue{
private int front, rear, max, cnt;
private int[] q;
public MyQueue(int a) {
// TODO Auto-generated constructor stub
front = 0;
rear = -1;
max = a;
cnt = 0;
q = new int[a];
}
public boolean isEmpty() {
return cnt == 0;
}
public void enqueue(int a) {
rear = (rear + 1) % max;
q[rear] = a;
cnt++;
}
public int dequeue() {
int a = q[front];
front = (front + 1) % max;
cnt--;
return a;
}
}
public class hugo_v2 {
static int row, col, hugox, hugoy, fi, li, oi, ans;
static int[][] diamond, fire, lake, out, visit;
static int[][] d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
static MyQueue fqx, fqy;
private static void bfsFire(){
int r, c, dr, dc;
while(!fqx.isEmpty()){
r = fqx.dequeue(); c = fqy.dequeue();
for(int i = 0; i < 4; i++){
dr = r + d[0][i]; dc = c + d[1][i];
if(dr >= 0 && dr < row && dc >= 0 && dc < col && fire[dr][dc] == -1 && lake[dr][dc] != 1){
fire[dr][dc] = fire[r][c] + 1;
fqx.enqueue(dr); fqy.enqueue(dc);
}
}
}
}
private static void backtrackHugo(int r, int c, int sum){
if(out[r][c] == 1){
if(ans < sum) ans = sum;
// return;
}
int dr, dc;
for(int i = 0; i < 4; i++){
dr = r + d[0][i]; dc = c + d[1][i];
if(dr >= 0 && dr < row && dc >= 0 && dc < col && visit[dr][dc] == -1){
if(lake[dr][dc] == 1){
visit[dr][dc] = visit[r][c] + 2;
backtrackHugo(dr, dc, sum + diamond[dr][dc]);
visit[dr][dc] = -1;
}
else if(visit[r][c] + 1 < fire[dr][dc] ||fire[dr][dc] == -1){
visit[dr][dc] = visit[r][c] + 1;
backtrackHugo(dr, dc, sum + diamond[dr][dc]);
visit[dr][dc] = -1;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// try {
// System.setIn(new FileInputStream("D:\\Trainee\\SRV_training\\src\\day16_2006\\hugo.txt"));
// } catch (FileNotFoundException e) {
// // TODO Auto-generated catch block
// e.printStackTrace();
// }
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
row = sc.nextInt(); col = sc.nextInt();
hugox = sc.nextInt() - 1; hugoy = sc.nextInt() - 1;
int a, b;
fi = sc.nextInt();
diamond = new int[row][col];
fire = new int[row][col];
lake = new int[row][col];
out = new int[row][col];
visit = new int[row][col];
fqx = new MyQueue(row * col);
fqy = new MyQueue(row * col);
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
fire[i][j] = -1;
visit[i][j] = -1;
}
}
visit[hugox][hugoy] = 0;
for(int i = 0; i < fi; i++){
a = sc.nextInt() - 1; b = sc.nextInt() - 1;
fire[a][b] = 0;
fqx.enqueue(a); fqy.enqueue(b);
}
li = sc.nextInt();
for(int i = 0; i < li; i++){
a = sc.nextInt() - 1; b = sc.nextInt() - 1;
lake[a][b] = 1;
}
oi = sc.nextInt();
for(int i = 0; i < oi; i++){
a = sc.nextInt() - 1; b = sc.nextInt() - 1;
out[a][b] = 1;
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
diamond[i][j] = sc.nextInt();
}
}
bfsFire();
ans = -1;
backtrackHugo(hugox, hugoy, diamond[hugox][hugoy]);
System.out.println("Case #" + tc);
System.out.println(ans);
}
}
}
#########################################################################################################
pipe network
package day16_2006;
import java.util.Scanner;
public class pipe_network {
static int[][] ngang = {{1, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{1, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{1, 0, 1, 1, 1, 0, 0},
{1, 0, 1, 1, 1, 0, 0}},
doc = {{1, 1, 0, 0, 1, 1, 0},
{1, 1, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 1, 1, 0}};
static int row, col, sx, sy, limit, ans;
static int startx, starty, endx, endy;
static int[][] visit;
static int[][] map;
private static void BFS(){
MyQueue qx = new MyQueue(row * col);
MyQueue qy = new MyQueue(row * col);
qx.enqueue(sx); qy.enqueue(sy);
int x, y, dx, dy, val1, val2;
while(!qx.isEmpty()){
x = qx.dequeue(); y = qy.dequeue();
val1 = map[x][y];
if(visit[x][y] < limit){
//up
dx = x - 1; dy = y;
if(dx >= 0 && visit[dx][dy] == 0){
val2 = map[dx][dy];
if(doc[val1][val2] == 1){
visit[dx][dy] = visit[x][y] + 1;
ans++;
qx.enqueue(dx); qy.enqueue(dy);
}
}
//right
dx = x; dy = y + 1;
if(dy < col && visit[dx][dy] == 0){
val2 = map[dx][dy];
if(ngang[val2][val1] == 1){
visit[dx][dy] = visit[x][y] + 1;
ans++;
qx.enqueue(dx); qy.enqueue(dy);
}
}
//down
dx = x + 1; dy = y;
if(dx <= endx && visit[dx][dy] == 0){
val2 = map[dx][dy];
if(doc[val2][val1] == 1){
visit[dx][dy] = visit[x][y] + 1;
ans++;
qx.enqueue(dx); qy.enqueue(dy);
}
}
//left
dx = x; dy = y - 1;
if(dy >= starty && visit[dx][dy] == 0){
val2 = map[dx][dy];
if(ngang[val1][val2] == 1){
visit[dx][dy] = visit[x][y] + 1;
ans++;
qx.enqueue(dx); qy.enqueue(dy);
}
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
row = sc.nextInt(); col = sc.nextInt();
sx = sc.nextInt(); sy = sc.nextInt();
limit = sc.nextInt();
visit = new int[row][col];
visit[sx][sy] = 1;
map = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
map[i][j] = sc.nextInt() - 1;
if(map[i][j] == -1) visit[i][j] = -1;
}
}
startx = sx - limit > 0 ? sx - limit : 0;
endx = sx + limit < row ? sx + limit : row - 1;
starty = sy - limit > 0 ? sy - limit : 0;
endy = sx + limit < col ? sy + limit : col - 1;
ans = 1;
BFS();
System.out.println("Case #" + tc + " " + ans);
}
}
}
#######################################################################################
mountain walking
package day17_2106;
import java.util.Scanner;
public class mountain_walkingv2 {
static int n, ans, max, min;
static int[][] map, d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
static boolean[] visit;
private static boolean bfs(int start, int end){
MyQueue qx = new MyQueue(n * n);
MyQueue qy = new MyQueue(n * n);
boolean[][] visit;
if(map[0][0] >= start && map[0][0] <= end){
qx.enqueue(0); qy.enqueue(0);
visit = new boolean[n][n];
visit[0][0] = true;
}
else return false;
int x, y, dx, dy;
while(!qx.isEmpty()){
x = qx.dequeue(); y = qy.dequeue();
for(int i = 0; i < 4; i++){
dx = x + d[0][i]; dy = y + d[1][i];
if(dx >= 0 && dy >= 0 && dx < n && dy < n && !visit[dx][dy] && map[dx][dy] >= start && map[dx][dy] <= end){
visit[dx][dy] = true;
qx.enqueue(dx); qy.enqueue(dy);
if(dx == n - 1 && dy == n - 1) return true;
}
}
}
return false;
}
private static boolean isValid(int mid){
for(int i = min; i <= max - mid; i++){
if(bfs(i, i + mid)) return true;
}
return false;
}
private static void solve(int dist, int left, int right){
while(!visit[dist]){
visit[dist] = true;
if(isValid(dist)){
ans = right = dist;
}
else{
left = dist;
}
dist = left + (right - left)/2;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
n = sc.nextInt();
max = 0; min = Integer.MAX_VALUE;
map = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = sc.nextInt();
if(map[i][j] < min) min = map[i][j];
if(map[i][j] > max) max = map[i][j];
}
}
ans = -1;
visit = new boolean[max + 1];
solve((max - min)/2, 0, max - min + 1);
System.out.println("#" + tc + " " + ans);
}
}
}
#########################################################################################################
ban bong
package day18_2206;
import java.util.Scanner;
public class ban_bong {
static int n;
static long score;
static int[] bubble, hoanvi;
static boolean[] visit;
private static long ban(int idx){
long mul = 1;
int left = idx, right = idx;
while(right < n && visit[right])right++;
while(left >= 0 && visit[left]) left--;
if(right >= n && left < 0) return bubble[idx];
if(right < n) mul *= bubble[right];
if(left >= 0) mul *= bubble[left];
return mul;
}
private static void solve(int cnt, long sum){
if(cnt == n){
score = score < sum ? sum : score;
}
for(int i = 0; i < n; i++){
if(!visit[i]){
visit[i] = true;
long tmp = ban(i);
solve(cnt + 1, sum + tmp);
visit[i] = false;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
n = sc.nextInt();
bubble = new int[n];
visit = new boolean[n];
for(int i = 0; i < n; i++){
bubble[i] = sc.nextInt();
}
score = 0;
solve(0, 0);
System.out.println("#" + tc + " " + score);
}
}
}
#####################################################################################################
minimal big sum
package day18_2206;
import java.util.Scanner;
public class minimal_big_sum {
static int k, n, ans, total, max;
static int[] numbers, blocks;
// private static int solve(){
// int max = 0;
// int start = 0, sum, j;
// for(int i = 1; i < k; i++){
// if(blocks[i] == n) return total;
// if(blocks[i] != 0){
// sum = 0; j = 0;
// while(j < blocks[i]){
// sum += numbers[start + j];
// j++;
// }
// start += blocks[i];
// max = max < sum ? sum : max;
// if(max >= ans) return ans;
// }
// }
// return max;
// }
// private static void sinh(int b, int cnt){
//
// if(b == k - 1){
// blocks[b] = n - cnt;
// int tmp = solve();
// if(ans > tmp) ans = tmp;
// return;
// }
//
// for(int i = 0; i <= n; i++){
// if(cnt + i <= n){
// blocks[b] = i;
// sinh(b + 1, cnt + i);
// }
// else break;
// }
// }
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
// k = sc.nextInt() + 1;
k = sc.nextInt();
n = sc.nextInt();
// blocks = new int[k];
total = 0; max = 0;
numbers = new int[n];
for(int i = 0; i < n; i++){
numbers[i] = sc.nextInt();
total += numbers[i];
max = max < numbers[i] ? numbers[i] : max;
}
ans = total;
// sinh(1, 0);
for(int i = max; i <= total; i++){
int sum = 0, cnt = 1;
for(int j = 0; j < n; j++){
if(sum + numbers[j] > i){
sum = numbers[j];
cnt++;
}
else{
sum += numbers[j];
}
}
if(cnt <= k){
ans = i;
break;
}
}
System.out.println("#" + tc + " " + ans);
}
}
}
###########################################################################
grid cell
package day19_2306;
import java.util.Scanner;
class MyQueue{
private int front, rear, max, cnt;
private int[] q;
public MyQueue(int a) {
// TODO Auto-generated constructor stub
front = 0;
rear = -1;
max = a;
cnt = 0;
q = new int[a];
}
public boolean isEmpty() {
return cnt == 0;
}
public void enqueue(int a) {
rear = (rear + 1) % max;
q[rear] = a;
cnt++;
}
public int dequeue() {
int a = q[front];
front = (front + 1) % max;
cnt--;
return a;
}
}
public class grid_cell {
static int row, col, xpour, ypour;
static int xSpecial, ySpecial, numMetal, time;
static int[][] map, d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
static int[][] visit;
static boolean fillS;
static MyQueue qx, qy;
private static void BFS(){
qx = new MyQueue(row * col);
qy = new MyQueue(row * col);
qx.enqueue(xpour); qy.enqueue(ypour);
fillS = false;
int x, y, dx, dy;
while(!qx.isEmpty()){
x = qx.dequeue(); y = qy.dequeue();
for(int i = 0; i < 4; i++){
dx = x + d[0][i]; dy = y + d[1][i];
if(dx < row && dy < col && dx >= 0 && dy >= 0 && visit[dx][dy]== 0 && map[dx][dy] == 1){
time = visit[dx][dy] = visit[x][y] + 1;
qx.enqueue(dx); qy.enqueue(dy);
if(checkSpecial() && !fillS){
visit[xSpecial][ySpecial] = visit[x][y] + 1;
fillS = true;
}
}
}
}
}
private static boolean checkMeltSpecial(){
int dx, dy;
for(int i = 0; i < 4; i++){
dx = xSpecial + d[0][i]; dy = ySpecial + d[1][i];
if(dx < 0 || dy < 0 || dx >= row || dy >= col || visit[dx][dy] == -1) return false;
}
return true;
}
private static boolean checkSpecial(){
int dx, dy;
for(int i = 0; i < 4; i++){
dx = xSpecial + d[0][i]; dy = ySpecial + d[1][i];
if(visit[dx][dy] == 0) return false;
}
return true;
}
private static boolean checkFullMelted(){
if(!fillS) return false;
else
{
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(visit[i][j] == 0) return false;
}
}
}
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
row = sc.nextInt(); col = sc.nextInt();
xpour = sc.nextInt() - 1; ypour = sc.nextInt() - 1;
map = new int[row][col];
visit = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
map[i][j] = sc.nextInt();
if(map[i][j] == 0) visit[i][j] = -1;
else if(map[i][j] == 2){
xSpecial = i; ySpecial = j;
}
}
}
System.out.println("Case #" + tc);
if(map[xpour][ypour] == 0 || !checkMeltSpecial()){
System.out.println(-1 + " " + -1);
}
else
{
visit[xpour][ypour] = 1;
BFS();
if(fillS) System.out.print(visit[xSpecial][ySpecial] + " ");
else System.out.print(-1 + " ");
if(!checkFullMelted()) System.out.println(-1);
else System.out.println(time);
}
}
}
}
#################################################################
package day19_2306;
import java.util.Scanner;
public class hugo_mat_ong {
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){
// visit[x][y] = true;
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) {
// TODO Auto-generated method stub
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);
}
// System.out.println("Case #1");
// System.out.println(2250000);
}
}
############################################################################################
package day19_2306;
import java.util.Scanner;
public class hugo_pha_dien {
static int n, cnt, island;
static boolean[] visit;
static int[][] map;
private static void reset(){
for(int i = 0; i < n; i++){
visit[i] = false;
}
}
private static void backTrack(int idx){
for(int i = 0; i < n; i++){
if(map[idx][i] == 1 && !visit[i]){
visit[i] = true;
backTrack(i);
}
}
}
private static int solve(int iln){
int cnt = 0;
for(int i = 0; i < n; i++){
if(!visit[i]){
cnt++;
visit[i] = true;
backTrack(i);
}
}
return cnt;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
n = sc.nextInt();
map = new int[n][n];
visit = new boolean[n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = sc.nextInt();
}
}
island = -1;
cnt = 1;
for(int i = 0; i < n; i++){
reset();
visit[i] = true;
int tmp = solve(i);
if(tmp > cnt){
island = i;
cnt = tmp;
}
}
System.out.println(island + 1);
}
}
}
Editor is loading...