code v1
unknown
plain_text
2 years ago
40 kB
9
Indexable
###################################################################
find cycle
import java.util.Scanner;
public class find_circle {
static boolean flag;
static int curNode, node, ed;
static boolean[] visit;
static int[][] edges;
private static void check(int idx){
// visit[]
for(int i = 0; i < ed; i++){
if(edges[i][0] == idx && !visit[i]){
visit[i] = true;
if(edges[i][1] == curNode){
flag = true;
return;
}
else check(edges[i][1]);
}
}
}
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++){
node = sc.nextInt(); ed = sc.nextInt();
edges = new int[ed][2];
for(int i = 0; i < ed; i++){
edges[i][0] = sc.nextInt();
edges[i][1] = sc.nextInt();
}
flag = false;
for(int i = 1; i <= node; i++){
visit = new boolean[ed];
curNode = i;
check(i);
if(flag) break;
}
System.out.println("Case #" + tc);
if(flag) System.out.println(1);
else System.out.println(0);
}
}
}
#################################################################
uniform distributiion in square
import java.util.Scanner;
class UStack {
private int maxSize;
private int[] stackArray;
private int top;
public UStack(int s) {
maxSize = s;
stackArray = new int[maxSize];
top = -1;
}
public void push(int j) {
stackArray[++top] = j;
}
public int pop() {
return stackArray[top--];
}
public int peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
}
public class uniform_distribution_in_square {
private static boolean checkSqare(int[][] board, int[][] trade, int n){
int x, y, count, d = 4, tx, ty;
int[][] direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(int i = 1; i <= n; i++){
count = 1;
x = trade[i][0]; y = trade[i][1];
UStack stackx = new UStack(2*n), stacky = new UStack(2*n);
stackx.push(x); stacky.push(y);
while(!stackx.isEmpty()){
x = stackx.pop(); y = stacky.pop();
board[x][y] = 0;
for(int j = 0; j < d; j++){
tx = x + direct[j][0]; ty = y + direct[j][1];
if(tx < 0 || tx > n || ty < 0 || ty > n) continue;
else if(board[tx][ty] == i){
count++;
stackx.push(tx); stacky.push(ty);
}
}
}
if(count < n) 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++){
int n = sc.nextInt();
int[][] board = new int[n + 1][n + 1];
int[][] trade = new int[n + 1][2];
for(int i = 1; i < n; i++){
for(int j = 0; j < n; j++){
int x = sc.nextInt(), y = sc.nextInt();
board[x][y] = i;
if(j == 0){
trade[i][0] = x;
trade[i][1] = y;
}
}
}
boolean check = false;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(board[i][j] == 0){
board[i][j] = n;
if(!check){
trade[n][0] = i; trade[n][1] = j;
check = true;
}
}
}
}
boolean result = checkSqare(board, trade, n);
System.out.println("Case #" + tc);
if(result){
System.out.println("good");
}
else System.out.println("wrong");
}
}
}
###############################################################################
move cow
import java.util.Scanner;
public class move_cow {
static int[] wcows;
static int n, max;
private static void sinh(int[] binary, int i, int w){
for(int j = 0; j < 2; j++){
binary[i] = j;
if(i == n - 1){
int sum = 0;
for(int k = 0; k < n; k++){
sum += binary[k] * wcows[k];
}
if(sum < w && max < sum) max = sum;
}
else sinh(binary, i + 1, w);
}
}
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++){
int w = sc.nextInt(); n = sc.nextInt();
wcows = new int[n];
for(int i = 0; i < n; i++){
wcows[i] = sc.nextInt();
}
int[] binary = new int[n];
max = 0;
sinh(binary, 0, w);
System.out.println("#" + tc + " " + max);
}
}
}
#####################################################################################
qua cau
import java.util.Scanner;
public class qua_cau {
static int count, m = 5, sum;
private static void calMoney(int[][]bridge, int row, int col, boolean check, int sum){
if(row == 0){
if(count < sum) count = sum;
return;
}
for(int i = -1; i <= 1; i++){
int r = row - 1, c = col + i;
if(c >= 0 && c < m){
if(bridge[r][c] < 2) calMoney(bridge, r, c, check, sum + bridge[r][c]);
else if(check){
calMoney(bridge, r, c, false, sum);
}
}
}
}
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++){
int n = sc.nextInt();
int[][] bridge = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
bridge[i][j] = sc.nextInt();
}
}
count = -1; sum = 0;
boolean check = true;
calMoney(bridge, n, m / 2, true, sum);
System.out.println("#" + tc + " " + count);
}
}
}
###################################################################################
sky map
import java.util.Scanner;
class Stack {
private int maxSize;
private int[] stackArray;
private int top;
public Stack(int s) {
maxSize = s;
stackArray = new int[maxSize];
top = -1;
}
public void push(int j) {
stackArray[++top] = j;
}
public int pop() {
return stackArray[top--];
}
public int peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
}
public class sky_map {
static int max, count, n, sum;
static int[][] sky, direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private static void countStar(int[][] sky, int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(sky[i][j] == 1){
count++;
Stack sx = new Stack(n * n), sy = new Stack(n * n);
sx.push(i); sy.push(j);
int buf = 1, x, y, nx, ny;
while(!sx.isEmpty()){
x = sx.pop(); y = sy.pop();
sky[x][y] = 0;
for(int k = 0; k < 4; k++){
nx = x + direct[k][0]; ny = y + direct[k][1];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if(sky[nx][ny] == 1){
buf++;
sx.push(nx); sy.push(ny);
sky[nx][ny] = 0;
}
}
}
if(max < buf) max = buf;
}
}
}
}
private static void countmap(int x, int y){
sky[x][y] = 0;
for(int i = 0; i < 4; i++){
int dx = x + direct[i][0], dy = y + direct[i][1];
if(dx >= 0 && dx < n && dy >= 0 && dy < n && sky[dx][dy] == 1){
sum++;
countmap(dx, 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++){
n = sc.nextInt();
sky = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
sky[i][j] = sc.nextInt();
}
}
max = 0; count = 0;
// countStar(sky, n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(sky[i][j] == 1){
count++; sum = 1;
countmap(i, j);
if(max < sum) max = sum;
}
}
}
System.out.println(count + " " + max);
}
}
}
###############################################################################################
queens
import java.util.Scanner;
public class queens {
static int n = 8, count;
static int[][] cases = new int[100][n];
static boolean[] col , diagup, diagdown;
static int [] trace = new int[n];
private static void check(int i) {
for(int j = 0; j < n; j++) {
if(!col[j] && !diagup[i - j + n - 1] && !diagdown[i + j]) {
trace[i] = j;
col[j] = true; diagup[i - j + n - 1] = true; diagdown[i + j] = true;
if(i == n - 1) {
// System.out.println("Case " + count);
for(int k = 0; k < n; k++) {
cases[count][k] = trace[k];
// System.out.print(cases[count][k] + " ");
}
count++;
// System.out.println();
}
else check(i + 1);
col[j] = false; diagup[i - j + n - 1] = false; diagdown[i + j] = false;
}
}
}
private static void check1(int x){
for(int i = 0; i < n; i++){
if(!col[i] && !diagup[x - i + n - 1] && !diagdown[x + i]){
col[i] = true; diagup[x - i + n - 1] = true; diagdown[x + i] = true;
trace[x] = i;
if(x == n - 1){
for(int j = 0; j < n; j++){
cases[count][j] = trace[j];
}
count++;
}
else check1(x + 1);
col[i] = false; diagup[x - i + n - 1] = false; diagdown[x + i] = false;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
count = 0;
col = new boolean[n]; diagup = new boolean[2 * n]; diagdown = new boolean[2 * n];
check(0);
int testcase = sc.nextInt();
int[][] board = new int[n][n];
for(int tc = 1; tc <= testcase; tc++) {
int nb = sc.nextInt();
System.out.println("Case #" + tc);
for(int i = 0; i < nb; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
board[j][k] = sc.nextInt();
}
}
int max = 0, sum;
for(int j = 0; j < count; j++) {
sum = 0;
for(int k = 0; k < n; k++) {
sum += board[k][cases[j][k]];
}
if(max < sum) max = sum;
}
System.out.println(max);
}
}
}
}
#########################################################################################################
lang mac
import java.util.Scanner;
public class village {
static int bound, iso, n;
static boolean[] visit;
static int[][] d = {{2, 0, 1}, {3, 1, 2}, {3, 0, 4}, {1, 0, 0}, {10, 10, 0}, {1, 0, 0}, {2, 0, 5}, {1, 0, 0}, {3, 2, 4},
{6, 5, 7}, {24, 23, 1}, {1, 0, 3}, {10, 9, 12}, {3, 2, 5}, {7, 5, 6}, {12, 5, 13}, {1, 0, 11},
{3, 2, 3}, {1, 0, 4}, {7, 6, 5}, {25, 25, 0}, {9, 5, 16}, {9, 8, 5}, {25, 25, 0}, {1, 0, 5}, {2, 1, 4},
{3, 2, 6}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0}, {1, 0, 1}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0},
{1, 0, 1}, {1, 0, 1}, {22, 16, 28}, {4, 2, 7}, {1, 0, 0}, {41, 36, 9}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0},
{2, 1, 3}, {1, 0, 0}, {40, 31, 10}, {2, 1, 1}, {1, 0, 0}, {300, 300, 0}}; ;
private static int checkBridge(int[][] road, int n){
boolean[] checked = new boolean[n];
int result = 0;
for(int i = 0; i < n; i++){
if(!checked[i]){
int count = 0, x = 0, y = 0;
for(int j = 0; j < n; j++){
if(road[i][j] == 1){
count++;
x = i; y = j;
}
}
if(count == 1){
checked[y] = true;
result++;
}
}
}
return result;
}
private static void check(int[][] road, int x){
visit[x] = true;
for(int i = 0; i < n; i++){
if(road[x][i] == 1){
if(!visit[i]){
check(road, i);
}
}
}
}
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();
int[][] road = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
road[i][j] = sc.nextInt();
}
}
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
if(road[i][j] == 1){
if(!visit[i]){
bound++;
visit[i] = true;
}
if(!visit[j]) check(road, j);
}
}
}
// d = {{2, 0, 1}, {3, 1, 2}, {3, 0, 4}, {1, 0, 0}, {10, 10, 0}, {1, 0, 0}, {2, 0, 5}, {1, 0, 0}, {3, 2, 4},
// {6, 5, 7}, {24, 23, 1}, {1, 0, 3}, {10, 9, 2}, {3, 2, 5}, {7, 5, 6}, {12, 5, 13}, {1, 0, 11},
// {3, 2, 3}, {1, 0, 4}, {7, 6, 5}, {25, 25, 0}, {9, 5, 16}, {9, 8, 5}, {25, 25, 0}, {1, 0, 5}, {2, 1, 4},
// {3, 2, 6}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0}, {1, 0, 1}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0},
// {1, 0, 1}, {1, 0, 1}, {22, 16, 28}, {4, 2, 7}, {1, 0, 0}, {41, 36, 9}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0},
// {2, 1, 3}, {1, 0, 0}, {40, 31, 10}, {2, 1, 1}, {1, 0, 0}, {300, 300, 0}};
// System.out.println((bound + iso)+ " " + iso + " " + bridge);
}
for(int i = 0; i < 50; i++){
System.out.println(d[i][0] + " " + d[i][1] + " " + d[i][2]);
}
}
}
######################################################################################################################
array game
import java.util.Scanner;
public class array_game {
static int n, max;
static int[] board;
private static long sumArr(int left, int right){
long sum = 0;
for(int i = left; i <= right; i++){
sum += board[i];
}
return sum;
}
private static void Try(int left, int right, int count, long sum){
if(count > max) max = count;
if(sum % 2 != 0) return;
else{
int mid = left;
while(mid <= right){
long sumlft = sumArr(left, mid);
if(sumlft == sum / 2){
break;
}
else if(sumlft > sum / 2){
return;
}
++mid;
}
if(mid > right) return;
Try(left, mid, count + 1, sum / 2);
Try(mid + 1, right, count + 1, sum / 2);
}
}
private static int checkSplit(int left, int right){
long total = sumArr(left, right);
if(total % 2 != 0) return -1;
total = total/2;
int mid = left;
while(mid <= right){
long sumlft = sumArr(left, mid);
if(sumlft == total) return mid;
else if(sumlft > total) return -1;
++mid;
}
return -1;
}
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();
board = new int[n];
int count0 = 0;
for(int i = 0; i < n; i++){
board[i] = sc.nextInt();
if(board[i] == 0) count0++;
}
if(count0 == n) max = n - 1;
else{
max = 0;
long sum = sumArr(0, n - 1);
Try(0, n - 1, 0, sum);
}
System.out.println(max);
}
}
}
############################################################################################
import java.util.Scanner;
public class turn_over_game {
static int[][] board, direct = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
static int n = 4, b = 0, w = 1, min = 0;
static boolean flag;
private static boolean check()
{
int buf = board[0][0];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(board[i][j] != buf) return false;
}
}
return true;
}
private static void change(int x, int y){
board[x][y] = 1 - board[x][y];
for(int i = 0; i < 4; i++){
int dx = x + direct[i][0], dy = y + direct[i][1];
if(dx >= 0 && dy >= 0 && dx < n && dy < n){
board[dx][dy] = 1 - board[dx][dy];
}
}
}
private static void Try(int x, int y, int count){
if(check()){
flag = true;
if(count < min) min = count;
return;
}
if(x >= n) return;
if(count > min) return;
if(y + 1 < n){
change(x, y);
Try(x, y + 1, count + 1);
change(x, y);
Try(x, y + 1, count);
}
else
{
change(x, y);
Try(x + 1, 0, count + 1);
change(x, y);
Try(x + 1, 0, count);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
board = new int[n][n];
sc.nextLine();
for(int tc = 1; tc <= testcase; tc++){
for(int i = 0; i < n; i++){
String line = sc.nextLine();
for(int j = 0; j < n; j++) {
if(line.charAt(j) == 'b') board[i][j] = b;
else board[i][j] = w;
}
}
flag = false;
min = Integer.MAX_VALUE;
Try(0, 0, 0);
System.out.println("Case #" + tc);
if(flag) System.out.println(min);
else System.out.println("impossible");
}
}
}
#####################################################################################
map coloring
import java.util.Scanner;
public class map_coloring {
static int[][] map;
static int[] color;
static boolean flag;
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++){
int countries = sc.nextInt(), borders = sc.nextInt();
map = new int[countries + 1][countries + 1]; color = new int[countries + 1];
int x, y;
for(int i = 0; i < borders; i++){
x = sc.nextInt(); y = sc.nextInt();
map[x][y] = 1; map[y][x] = 1;
}
for(int i = 1; i <= countries; i++){
color[i] = -1;
}
color[1] = 0;
MyQueue cntr = new MyQueue(countries * countries);
cntr.enqueue(1);
int buf;
flag = true;
while(!cntr.isEmpty()){
buf = cntr.dequeue();
for(int i = 1; i <= countries; i++){
if(map[buf][i] == 1){
if(color[i] == -1){
color[i] = 1 - color[buf];
cntr.enqueue(i);
}
else if(color[i] != 1 - color[buf]){
flag = false;
break;
}
}
}
if(!flag) break;
}
System.out.print("#" + tc + " ");
if(flag){
for(int i = 1; i <= countries; i++){
System.out.print(color[i]);
}
}
else System.out.print(-1);
System.out.println();
}
}
}
##########################################################################################
magnetic nam cham
import java.util.Scanner;
public class magnetic {
static int testcase = 10;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
for(int tc = 0; tc < testcase; tc++){
int n = sc.nextInt();
int[][] board = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
board[i][j] = sc.nextInt();
}
}
int count = 0;
boolean check = true;
for(int i = 0; i < n; i++){
check = false;
for(int j = 0; j < n; j++){
if(board[j][i] == 1){
check = true;
}
if(check && board[j][i] == 2){
count++;
check = false;
}
}
}
System.out.println("#" + tc + " " + count);
}
}
}
###########################################################################################
painting
import java.util.Scanner;
public class painting {
static int n, value;
static int[] d = {0, 1, 2, 3};
static int[][] map;
static int[] color;
private static boolean check(int v, int i){
for(int j = 0; j < n; j++){
if(map[v][j] == 1 && color[j] == i)
return false;
}
return true;
}
private static void Try(int v){
if(v == n){
value++;
return;
}
for(int i = 0; i < 4; i++){
if(check(v, i)){
color[v] = i;
Try(v + 1);
color[v] = -1;
}
}
}
public static void main(String[] args) {
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];
color = new int[n];
for(int i = 0; i < n; i++){
color[i] = -1;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = sc.nextInt();
}
}
value = 0;
Try(0);
System.out.println("Case #" + tc);
System.out.println(value);
}
}
}
#######################################################################################
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class protect_farm {
static int[][] map, d = {{-1, -1, -1, 0, 1, 1, 1, 0}, {-1, 0, 1, 1, 1, 0, -1, -1}};
static int row, col, cntTop;
static boolean[][] visit;
static MyQueue sx, sy;
private static void BFS(int x, int y){
visit[x][y] = true;
sx.enqueue(x);sy.enqueue(y);
int tmp = 1, r, c, dr, dc;
while(!sx.isEmpty()){
r = sx.dequeue(); c = sy.dequeue();
for(int i = 0; i < 8; i++){
dr = r + d[0][i]; dc = c + d[1][i];
if(dr >= 0 && dr < row && dc >= 0 && dc < col){
if(map[dr][dc] == map[r][c] && !visit[dr][dc]){
visit[dr][dc] = true;
sx.enqueue(dr); sy.enqueue(dc);
}
else if(map[dr][dc] > map[r][c]){
tmp = 0;
}
}
}
}
cntTop += tmp;
}
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
System.setIn(new FileInputStream("D:\\Trainee\\SRV_training\\src\\day11_1306\\input.txt"));
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
row = sc.nextInt(); col = sc.nextInt();
map = new int[row][col]; visit = new boolean[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] = true;
}
}
cntTop = 0;
// sx.reset(); sy.reset();
sx = new MyQueue(row * col + 1);
sy = new MyQueue(row * col + 1);
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(!visit[i][j]){
visit[i][j] = true;
BFS(i, j);
}
}
}
System.out.println("#" + tc + " " + cntTop);
}
}
}
##############################################################################
connect processor
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class connect_processor {
static int n, ans, npro;
// static int[] pro;
static int[][] map, processor, d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
static boolean[][] visit, tmp;
private static void reset(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
visit[i][j] = false;
}
}
}
private static int check(int p, int i){
int tmp = 0, k = 1, dx, dy;
{
while(true){
dx = processor[p][0] + k * d[i][0];
dy = processor[p][1] + k * d[i][1];
if(dx < 0 || dy < 0 || dx >= n || dy >= n) break;
if(visit[dx][dy]){
tmp = 0;
// flag++;
break;
}
else{
tmp++;
}
k++;
}
}
return tmp;
}
private static boolean unconnect(int p){
int tmp = 0, k = 1, dx, dy;
for(int i = 0; i < 4; i++){
while(true){
dx = processor[p][0] + k * d[i][0];
dy = processor[p][1] + k * d[i][1];
if(dx < 0 || dy < 0 || dx >= n || dy >= n) break;
if(map[dx][dy] == 1){
tmp++;
break;
}
k++;
}
}
if(tmp == 4) return true;
else return false;
}
private static void solve(int p, int cnt){
if(cnt > ans) return;
if(p == npro){
if(cnt < ans){
ans = cnt;
}
return;
}
int dx, dy, k, tmp, flag = 0;
for(int i = 0; i < 4; i++){
tmp = check(p, i);
if(tmp == 0) ++flag;
else if(tmp > 0 || (flag == 4 && unconnect(p))){
for(int j = 1; j <= tmp; j++){
dx = processor[p][0] + j * d[i][0];
dy = processor[p][1] + j * d[i][1];
visit[dx][dy] = true;
}
solve(p + 1, cnt + tmp);
for(int j = 1; j <= tmp; j++){
dx = processor[p][0] + j * d[i][0];
dy = processor[p][1] + j * d[i][1];
visit[dx][dy] = false;
}
}
}
}
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
System.setIn(new FileInputStream("D:\\Trainee\\SRV_training\\src\\day12_1406\\processor.txt"));
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
n = sc.nextInt();
processor = new int[n * n][2];
npro = 0;
map = new int[n][n]; visit = new boolean[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] == 1){
visit[i][j] = true;
if(i != 0 && j != 0 && i != n - 1 && j != n - 1){
processor[npro][0] = i;
processor[npro][1] = j;
npro++;
}
}
}
}
int min = Integer.MAX_VALUE;
ans = min;
solve(0, 0);
if(ans == min) ans = 21;
System.out.println("#" + tc + " " + ans);
}
}
}
##########################################################################################
gold mining
import java.util.Scanner;
public class gold_miningv1 {
static int n, m, maxlen, mincost;
static int[][] map, cost, gold, d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
static boolean[][] visit;
private static void reset(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(map[i][j] == 0) visit[i][j] = true;
else visit[i][j] = false;
}
}
}
private static void go(int x, int y){
cost = new int[n][n];
cost[x][y] = 0;
reset();
visit[x][y] = true;
int g = 0;
int len = 0;
MyQueue qx = new MyQueue(n * n);
MyQueue qy = new MyQueue(n * n);
qx.enqueue(x); qy.enqueue(y);
int dx, dy;
while(!qx.isEmpty()){
x = qx.dequeue(); y = qy.dequeue();
for(int j = 0; j < 4; j++){
dx = x + d[0][j]; dy = y + d[1][j];
if(dx < n && dy < n && dx >= 0 && dy >= 0 && map[dx][dy] != 0 && !visit[dx][dy]){
visit[dx][dy] = true;
qx.enqueue(dx); qy.enqueue(dy);
cost[dx][dy] = cost[x][y] + 1;
if(map[dx][dy] == 2){
++g;
if(cost[dx][dy] > len) len = cost[dx][dy];
}
}
}
}
if(maxlen > len && g != 0) {
maxlen = len;
}
}
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(); m = sc.nextInt();
map = new int[n][n]; gold = new int[2][m];
visit = new boolean[n][n];
for(int i = 0; i < m; i++){
gold[0][i] = sc.nextInt() - 1;
gold[1][i] = sc.nextInt() - 1;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = sc.nextInt();
}
}
for(int i = 0; i < m; i++){
map[gold[0][i]][gold[1][i]] = 2;
}
maxlen = Integer.MAX_VALUE; mincost = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(map[i][j] == 1){
go(i, j);
}
}
}
System.out.println("Case #" + tc);
System.out.println(maxlen);
}
}
}
##################################################################################################
sky force
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class sky_force {
static int row, col = 5,coins;
static int[][] map;
static int[][] bomb;
private static void reset(){
for(int i = 0; i < 2; i++){
for(int j = 0; j < col * col; j++){
bomb[i][j] = 0;
}
}
}
private static void go(int r, int c, int cnt, boolean flag){
if(r < 0){
if(cnt > coins) coins = cnt;
return;
}
int dc;
for(int i = -1; i <= 1; i++){
dc = c + i;
if(dc >= 0 && dc < col){
if(map[r][dc] < 2){
go(r - 1, dc,cnt + map[r][dc], flag);
}
else{
if(flag){
reset();
int del = 0;
int tmp = r - 5 + 1;
if(tmp < 0) tmp = 0;
for(int j = tmp; j <= r; j++){
for(int k = 0; k < col; k++){
if(map[j][k] == 2){
map[j][k] = 0;
bomb[0][del] = j;bomb[1][del] = k;
del++;
}
}
}
go(r - 1, dc, cnt, false);
for(int j = 0; j < del; j++){
map[bomb[0][j]][bomb[1][j]] = 2;
}
}
else go(r - 1, dc, cnt - 1, false);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
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();
}
}
coins = -1;
bomb = new int[2][col * col];
go(row - 1, col/2, 0, true);
System.out.println("Case #" + tc);
System.out.println(coins);
}
}
}
########################################################################################################
frog
package day14_1606;
import java.util.Scanner;
public class frog {
static int near = 40 * 40, far = 90 * 90, jn = 1, jf = 2, l, rleaf;
static int startx, starty, endx, endy, curx, cury, curi;
static int ansf, ansn;
static int x = 0, y = 1, r = 2;
static int[][] leaf;
static int[] dist, visit, index;
private static int calLen(int i1, int i2){
int l1 = (leaf[x][i1] - leaf[x][i2]) * (leaf[x][i1] - leaf[x][i2]);
int l2 = (leaf[y][i1] - leaf[y][i2]) * (leaf[y][i1] - leaf[y][i2]);
int lr = leaf[r][i1] * leaf[r][i1] + leaf[r][i2]*leaf[r][i2];
int ans = l1 + l2 - lr;
return ans;
}
private static void getDist(int idx){
for(int i = 0; i < l; i++){
if(i != idx && visit[i] == 0){
int tmp = calLen(idx, i) + dist[idx];
if(dist[i] > tmp){
dist[i]= tmp;
index[i] = idx;
}
}
}
return;
}
private static void cnt(int n){
if(n == 0) return;
if(visit[n] == 2) ansf++;
else if(visit[n] == 1) ansn++;
cnt(index[n]);
}
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++){
l = sc.nextInt();
leaf = new int[3][l];
for(int i = 0; i < l; i++){
leaf[x][i] = sc.nextInt();
leaf[y][i] = sc.nextInt();
leaf[r][i] = sc.nextInt();
}
dist = new int[l];
for(int i = 1; i < l; i++){
dist[i] = Integer.MAX_VALUE;
}
visit = new int[l]; index = new int[l];
visit[0] = -1;
// startx = leaf[x][0]; starty = leaf[y][0];
endx = leaf[x][l - 1]; endy = leaf[y][l - 1];
// curx = startx; cury = starty; curi = 0;
curi = 0; ansn = 0; ansf = 0;
boolean flag = false;
while(true){
int idx = 0, min = Integer.MAX_VALUE;
getDist(curi);
for(int i = 0; i < l; i++){
if(visit[i] == 0 && dist[i] < min){
// curx = leaf[x][i];
// cury = leaf[y][i];
min = dist[i];
idx = i;
}
}
curi = idx;
if(min > far){
flag = true;
break;
}
else{
if(min <= far && min >near){
// ansf++;
visit[curi] = jf;
}
else{
// ansn++;
visit[curi] = jn;
}
// idx++;
// if(curx == endx && cury == endy){
if(curi == l - 1){
break;
}
}
}
if(!flag){
cnt(l - 1);
System.out.println(ansf + " " + ansn);
}
else System.out.println(-1);
}
}
}
######################################################################################
pizza location
##################################################################################
battle city
package day15_1906;
import java.util.Scanner;
public class battle_city {
static int Y = 0, T = 1, S = 2, B = 3, E = 4, R = 5;
static int startx, starty, endx, endy, row, col;
static int[][] map, visit, direct = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
static MyQueue qx, qy;
private static void reset(){
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
visit[i][j] = Integer.MAX_VALUE;
}
}
}
private static void DJS(int x, int y){
qx.enqueue(x); qy.enqueue(y);
int dx, dy;
while(!qx.isEmpty()){
x = qx.dequeue(); y = qy.dequeue();
for(int i = 0; i < 4; i++){
dx = x + direct[0][i]; dy = y + direct[1][i];
if(dx >= 0 && dy >= 0 && dx < row && dy < col){
if(map[dx][dy] != S &&map[dx][dy] != R){
int tmp = 0;
if(map[dx][dy] == E || map[dx][dy] == T){
tmp = visit[x][y] + 1;
}
else if(map[dx][dy] == B){
tmp = visit[x][y] + 2;
}
if(visit[dx][dy] > tmp){
visit[dx][dy] = tmp;
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();
map = new int[row][col];
sc.nextLine();
for(int i = 0; i < row; i++){
String line = sc.nextLine();
for(int j = 0; j < col; j++){
char c = line.charAt(j);
if(c == 'B') map[i][j] = B;
else if(c == 'S') map[i][j] = S;
else if(c == 'R') map[i][j] = R;
else if(c == 'Y'){
startx = i;
starty = j;
map[i][j] = Y;
}
else if(c == 'T'){
map[i][j] = T;
endx = i;
endy = j;
}
else map[i][j] = E;
}
}
visit = new int[row][col];
qx = new MyQueue(row * col);
qy = new MyQueue(row * col);
reset();
visit[startx][starty] = 0;
DJS(startx, starty);
System.out.println("Case #" + tc);
if(visit[endx][endy] == Integer.MAX_VALUE)
System.out.println(-1);
else System.out.println(visit[endx][endy]);
}
}
}
####################################################################################################
cleaning robot
package day15_1906;
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 cleaning_robot {
static int row, col, dirt, step, x = 0, y = 1;
static int[][] map, idxDirt, distance, temp, direct = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static boolean[][] visit;
static boolean[] visitD;
static MyQueue qx, qy;
private static int BFS(int x1, int y1, int x2, int y2){
qx = new MyQueue(row * col);
qy = new MyQueue(row * col);
reset();
qx.enqueue(x1); qy.enqueue(y1);
int r, c, dr, dc;
while(!qx.isEmpty()){
r = qx.dequeue(); c = qy.dequeue();
for(int i = 0; i < 4; i++){
dr = r + direct[i][0]; dc = c + direct[i][1];
if(dr >= 0 && dc >= 0 && dr < row && dc < col && !visit[dr][dc] && map[dr][dc] != 2){
temp[dr][dc] = temp[r][c] + 1;
visit[dr][dc] = true;
qx.enqueue(dr);
qy.enqueue(dc);
}
if(dr == x2 && dc == y2){
return temp[dr][dc];
}
}
}
return 0;
}
private static void reset(){
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
visit[i][j] = false;
temp[i][j] = 0;
}
}
}
private static void solve(int d, int cnt, int sum){
if(cnt == dirt - 1){
if(step > sum) step = sum;
return;
}
if(sum > step) return;
for(int i = 1; i < dirt; i++){
if(!visitD[i]){
visitD[i] = true;
solve(i, cnt + 1, sum + distance[d][i]);
visitD[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++) {
row = sc.nextInt(); col = sc.nextInt();
map = new int[row][col];
visit = new boolean[row][col];
dirt = 1;
idxDirt = new int[2][12];
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
map[i][j] = sc.nextInt();
if(map[i][j] == 1) {
idxDirt[x][dirt] = i;
idxDirt[y][dirt] = j;
dirt++;
}
else if(map[i][j] == 3) {
idxDirt[x][0] = i;
idxDirt[y][0] = j;
}
}
}
distance = new int[dirt][dirt];
visit = new boolean[row][col];
temp = new int[row][col];
for(int i = 0; i < dirt - 1; i++){
for(int j = i + 1; j < dirt; j++){
if(i != j){
int tmp = BFS(idxDirt[x][i], idxDirt[y][i], idxDirt[x][j], idxDirt[y][j]);
distance[i][j] = tmp;
distance[j][i] = tmp;
}
}
}
boolean flag = true;
for(int i = 0; i < dirt; i++){
int sum = 0;
for(int j = 0; j < dirt; j++){
sum += distance[i][j];
}
if(sum == 0){
flag = false;
break;
}
}
System.out.println("Case #" + tc);
if(!flag){
System.out.println(-1);
}
else{
visitD = new boolean[dirt];
step = Integer.MAX_VALUE;
visitD[0] = true;
solve(0, 0, 0);
System.out.println(step);
}
}
}
}
###################################################################################3
fast robot
package day15_1906;
import java.util.Scanner;
public class fast_robot {
static int row, col, sx, sy, ex, ey;
static int val, N = 1, D = 2;
static int[] step;
static int[][] map, trace, direct = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
static boolean flag;
static boolean[][] visit;
static MyQueue qx, qy;
private static void BFS(int x, int y){
qx.enqueue(x); qy.enqueue(y);
int dx, dy;
while(!qx.isEmpty()){
x = qx.dequeue(); y = qy.dequeue();
for(int i = 0; i < 4; i++){
dx = x + direct[i][0]; dy = y + direct[i][1];
while(dx >= 0 && dy >= 0 && dx < row && dy < col && map[dx][dy] == 0){
if(trace[dx][dy] == -1){
trace[dx][dy] = trace[x][y] + 1;
qx.enqueue(dx); qy.enqueue(dy);
}
if(dx == ex && dy == ey) return;
dx = dx + direct[i][0]; dy = dy + direct[i][1];
}
}
}
}
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();
sy = sc.nextInt() - 1; sx = sc.nextInt() - 1;
ey = sc.nextInt() - 1; ex = sc.nextInt() - 1;
sc.nextLine();
map = new int[row][col];
for(int i = 0; i < row; i++){
String line = sc.nextLine();
for(int j = 0; j < col; j++){
map[i][j] = Integer.parseInt(Character.toString(line.charAt(j)));
}
}
step = new int[row*col];
val = Integer.MAX_VALUE; flag = false;
qx = new MyQueue(row * col);
qy = new MyQueue(row * col);
trace = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
trace[i][j] = -1;
}
}
BFS(sx, sy);
System.out.println(trace[ex][ey]);
}
}
}
###################################################################################
Editor is loading...