D2008
///////////////////////////////// package d2008; import java.util.Scanner; public class MoiDamCuoi { static int t,n,m,u,v; static int[][] a = new int[n+1][n+1]; static int[] visit = new int[n+1]; static class Queue{ int front,rear; int[] data = new int[90001]; public Queue(){ front = rear = 0; } public void enQ(int n){ data[rear++] = n; } public int deQ(){ return data[front++]; } public int qPeek(){ return data[front]; } public boolean isEmpty(){ if(front == rear){ return true; } return false; } } public static boolean BFS(int u, int v){ Queue q = new Queue(); q.enQ(u); visit[u] = 1; while(!q.isEmpty()){ int nx = q.deQ(); for(int i = 1 ; i <= n ; i++){ if(a[nx][i] == 1 && visit[i] == 0 ){ visit[i] = 1; q.enQ(i); } } if(nx == v){ return true; } } return false; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for(int tc = 1 ; tc <= t ; tc++){ n = sc.nextInt(); m = sc.nextInt(); u = sc.nextInt(); v = sc.nextInt(); a = new int[n+1][n+1]; visit = new int[n+1]; for(int i = 0 ; i < m ; i++){ int x = sc.nextInt(); int y = sc.nextInt(); a[x][y] = 1; } int res = 0; for(int i = 1 ; i <= n ; i++){ if(i == u || i == v){ continue; } visit = new int[n+1]; visit[i] = 1; if(!BFS(u, v)){ res++; } } System.out.println(res); System.out.println(); } } } ////////////////// package d2008; import java.util.Scanner; public class DiAnCuoi { static int t,n,m; static int[][] a = new int[n+1][n+1]; static int[] visit = new int[n+1]; static int res = 99999999; public static void Try(int k,int cnt){ if(cnt > res ){ return; } if(visit[1]==2){ if(visit[2] == 1){ res = Math.min(res, cnt); } return; } for(int i = 1 ; i <= n ; i++){ if(a[k][i] == 1){ if(visit[i] == 0){ visit[i] = 1; Try(i, cnt+1); visit[i] =0; } if(visit[i] == 1){ visit[i]++; Try(i, cnt); visit[i]--; } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for(int tc = 1 ; tc <= t; tc++){ n = sc.nextInt(); m = sc.nextInt(); a = new int[n+1][n+1]; visit = new int[n+1]; for(int i = 0 ; i < m ; i++){ int x = sc.nextInt(); int y = sc.nextInt(); a[x][y] = 1; } res = 99999999; visit[1]=1; Try(1, 1); System.out.println(res); } } } //////////////////////////// package d2008; import java.util.Scanner; public class HugoGiaoHang { static int t,sx,sy,hx,hy,n; static int[][] a = new int[n+1][2]; static boolean[] visit = new boolean[n+1]; public static int cal(int x1,int y1,int x2,int y2){ return Math.abs(x1-x2)+Math.abs(y1-y2); } static int res = 99999999; public static void Try(int k,int cnt,int prev){ if(k == n+1){ int tmp = cal(hx, hy, a[prev][0], a[prev][1]); if(res > cnt + tmp){ res = cnt +tmp; } } if(cnt > res){ return; } for(int i = 1 ; i <= n ; i++){ if(visit[i] == false){ visit[i] = true; int tmp = cal(a[prev][0], a[prev][1], a[i][0], a[i][1]); Try(k+1, cnt+tmp, i); visit[i] = false; } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for(int tc = 1 ; tc <= t ; tc++){ sx = sc.nextInt(); sy = sc.nextInt(); hx = sc.nextInt(); hy = sc.nextInt(); n = sc.nextInt(); a = new int[n+1][2]; a[0][0]= sx; a[0][1]= sy; visit = new boolean[n+1]; for(int i = 1 ; i <= n ; i++){ a[i][0] = sc.nextInt(); a[i][1] = sc.nextInt(); } res = 99999999; Try(1, 0, 0); System.out.println("Case #"+tc+" " +res); } } } ////////////////////////// package d2008; import java.util.Scanner; public class HugoDaoVangLevel4 { static int t, n, g; static int[][] a = new int[n][n]; static int[][] movang = new int[g][2]; static int res = 9999999; static int[][] visit = new int[n][n]; static int[][] step = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } }; static class Queue { int front, rear; int[] data = new int[90001]; public Queue() { front = rear = 0; } public void enQ(int n) { data[rear++] = n; } public int deQ() { return data[front++]; } public int qPeek() { return data[front]; } public boolean isEmpty() { if (front == rear) { return true; } return false; } } public static boolean checkMoVang(int r, int c) { for (int i = 0; i < g; i++) { if (movang[i][0] == r + 1 && movang[i][1] == c + 1) { return true; } } return false; } public static int solve() { int cnt = 0; for (int i = 0; i < g; i++) { if (visit[movang[i][0] - 1][movang[i][1] - 1] > cnt) { cnt = visit[movang[i][0] - 1][movang[i][1] - 1]; } } return cnt; } public static void BFS(int r, int c) { Queue qx = new Queue(); Queue qy = new Queue(); qx.enQ(r); qy.enQ(c); visit[r][c] = 1; while (!qx.isEmpty() && !qy.isEmpty()) { int nx = qx.deQ(); int ny = qy.deQ(); for (int i = 0; i < 4; i++) { int tmpx = nx + step[i][0]; int tmpy = ny + step[i][1]; if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n && visit[tmpx][tmpy] == 0 && a[tmpx][tmpy] == 1) { visit[tmpx][tmpy] = visit[nx][ny] + 1; qx.enQ(tmpx); qy.enQ(tmpy); } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for (int tc = 1; tc <= t; tc++) { n = sc.nextInt(); g = sc.nextInt(); a = new int[n][n]; movang = new int[g][2]; visit = new int[n][n]; for (int i = 0; i < g; i++) { movang[i][0] = sc.nextInt(); movang[i][1] = sc.nextInt(); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = sc.nextInt(); } } res = 9999999; int x = -1, y = -1; int dem = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == 1 && !checkMoVang(i, j)) { visit = new int[n][n]; BFS(i, j); int tmp = solve(); int dem1 = 0; for (int k = 0; k < g; k++) { if (visit[movang[k][0] - 1][movang[k][1] - 1] != 0) { dem1++; } } if(dem1 == dem){ if(res > tmp && tmp!=0){ res = tmp; x = i; y = j; } } else if(dem1 > dem){ dem = dem1; res = tmp; x = i; y = j; } } } } System.out.println("Case #" + tc); if (res == 9999999) { System.out.println(-1); } else { System.out.println(res-1); visit = new int[n][n]; BFS(x, y); for (int i = 0; i < g; i++) { if (visit[movang[i][0] - 1][movang[i][1] - 1] == 0) { System.out.println(movang[i][0] + " " + movang[i][1]); } } } } } } ///////////////////////////// package d2008; import java.util.Scanner; public class HugoDaoVang { static int t,n,g; static int[][] a = new int[n][n]; static int[][] movang = new int[g][2]; static int res = 9999999; static int[][] visit = new int[n][n]; static int[][] step = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; static class Queue{ int front,rear; int[] data = new int[90001]; public Queue(){ front = rear = 0; } public void enQ(int n){ data[rear++] = n; } public int deQ(){ return data[front++]; } public int qPeek(){ return data[front]; } public boolean isEmpty(){ if(front == rear){ return true; } return false; } } public static boolean checkMoVang(int r,int c){ for(int i = 0 ; i < g ; i++){ if(movang[i][0] == r+1 && movang[i][1] == c+1){ return true; } } return false; } public static int solve(){ int cnt = 0; int dem = 0; for(int i = 0 ; i < g ; i++){ if(visit[movang[i][0]-1][movang[i][1]-1] > cnt ){ cnt = visit[movang[i][0]-1][movang[i][1]-1]; } if(visit[movang[i][0]-1][movang[i][1]-1] != 0){ dem++; } } if(dem == g){ return cnt; } return 0; } public static void BFS(int r,int c){ Queue qx = new Queue(); Queue qy = new Queue(); qx.enQ(r); qy.enQ(c); visit[r][c] = 0; while(!qx.isEmpty() && !qy.isEmpty()){ int nx = qx.deQ(); int ny = qy.deQ(); for(int i = 0 ; i < 4 ; i++){ int tmpx = nx + step[i][0]; int tmpy = ny + step[i][1]; if(tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n && visit[tmpx][tmpy] == 0 && a[tmpx][tmpy] == 1){ visit[tmpx][tmpy] = visit[nx][ny]+1; qx.enQ(tmpx); qy.enQ(tmpy); } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for(int tc = 1 ; tc <= t ; tc++){ n = sc.nextInt(); g = sc.nextInt(); a = new int[n][n]; movang = new int[g][2]; visit = new int[n][n]; for(int i = 0 ; i < g ; i++){ movang[i][0] = sc.nextInt(); movang[i][1] = sc.nextInt(); } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ a[i][j] = sc.nextInt(); } } res = 9999999; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ if(a[i][j] == 1 && !checkMoVang(i, j)){ visit = new int[n][n]; BFS(i, j); int tmp = solve(); if(res > tmp && tmp!=0){ res = tmp; } } } } System.out.println("Case #"+tc); if(res == 9999999){ System.out.println(-1); } else{ System.out.println(res); } } } }
Leave a Comment