Untitled
unknown
plain_text
2 years ago
5.9 kB
6
Indexable
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class BaoVeNongTrang { static int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }; static int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 }; static int a[][]; static int Qx[]; static int Qy[]; static int visit[][]; static int n, m; static int res; public static int BFS(int x, int y) { int front = 0; int rear = 0; Qx[rear] = x; Qy[rear] = y; rear++; visit[x][y] = 1; res = 1; while (front != rear) { int tmpx = Qx[front]; int tmpy = Qy[front]; front++; for (int i = 0; i < 8; i++) { int xx = tmpx + dx[i]; int yy = tmpy + dy[i]; if ( visit[xx][yy] == 0 && a[xx][yy] == a[x][y]) { visit[xx][yy] = 1; Qx[rear] = xx; Qy[rear] = yy; rear++; } else if ( a[x][y] < a[xx][yy]) res = 0; } } return res; } public static void main(String[] args) { try { System.setIn(new FileInputStream("BaoVeNongTrang")); } catch (FileNotFoundException e) { e.printStackTrace(); } Scanner sc = new Scanner(System.in); int numTest = sc.nextInt(); for (int tc = 1; tc <= numTest; tc++) { n = sc.nextInt(); m = sc.nextInt(); a = new int[n + 2][m + 2]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] = sc.nextInt(); } } Qx = new int[705]; Qy = new int[705]; visit = new int[n + 2][m + 2]; res = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (visit[i][j] == 0 && a[i][j] != 0) { res += BFS(i, j); } } } System.out.println("#" + tc + " " + res); } } } import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class QuaCau { static int N, a[][]; static int dx[] = { -1, -1, -1 }; static int dy[] = { -1, 0, 1 }; static int visit[][]; static int d[][]; static int van, ans; public static void main(String[] args) { try { System.setIn(new FileInputStream("QuaCau")); } catch (FileNotFoundException e) { e.printStackTrace(); } Scanner sc = new Scanner(System.in); int numTest = sc.nextInt(); for (int tc = 1; tc <= numTest; tc++) { N = sc.nextInt(); a = new int[N + 2][6]; for (int i = 0; i < N; i++) { for (int j = 0; j < 5; j++) a[i][j] = sc.nextInt(); } visit = new int[N + 2][6]; van = 1; ans = -1; backTrack(0, N, 2); System.out.println("#" + tc + " " + ans); // for (int i = 0; i < N; i++) { // for (int j = 0; j < 5; j++) // System.out.print(a[i][j]+" "); // System.out.println(); // } } } public static boolean inMatrix(int x, int y) { if (x >= 0 && x < N && y >= 0 && y < 5) return true; return false; } public static int numXu(int x, int y) { if (a[x][y] == 1) return 1; return 0; } public static void backTrack(int sumMoney, int x, int y) { if (x == 0) { ans = Math.max(ans, sumMoney); } for (int i = 0; i < 3; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (inMatrix(xx, yy) && visit[xx][yy] == 0) { if (a[xx][yy] != 2) { visit[xx][yy] = 1; backTrack(sumMoney + numXu(xx, yy), xx, yy); visit[xx][yy] = 0; } else if (a[xx][yy] == 2 && van == 1) { van = 0; visit[xx][yy] = 1; visit[xx][yy] = 1; backTrack(sumMoney + numXu(xx, yy), xx, yy); visit[xx][yy] = 0; van = 1; } } } } } import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class pizzaFinal { static int K, R, M, N, ans, sumPeople; static int xLocation[], yLocation[]; static int xSoli[], ySoli[], numPeople[]; static boolean isphucVu[][]; static boolean visitSoli[]; public static void main(String[] args) { long startTime = System.currentTimeMillis(); try { System.setIn(new FileInputStream("pizza")); } catch (FileNotFoundException e) { e.printStackTrace(); } Scanner sc = new Scanner(System.in); int numTest = sc.nextInt(); for (int tc = 1; tc <= numTest; tc++) { K = sc.nextInt(); R = sc.nextInt(); M = sc.nextInt(); xLocation = new int[M]; yLocation = new int[M]; for (int i = 0; i < M; i++) { xLocation[i] = sc.nextInt(); yLocation[i] = sc.nextInt(); } N = sc.nextInt(); xSoli = new int[N]; ySoli = new int[N]; numPeople = new int[N]; for (int i = 0; i < N; i++) { xSoli[i] = sc.nextInt(); ySoli[i] = sc.nextInt(); numPeople[i] = sc.nextInt(); } isphucVu = new boolean[M][N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { double d = Math.sqrt(Math.pow(xSoli[j] - xLocation[i], 2) + Math.pow(ySoli[j] - yLocation[i], 2)); if (d <= R) isphucVu[i][j] = true; } } visitSoli = new boolean[N]; ans = 0; backTrack(0, 0, 0); System.out.println("#" + tc + " " + ans); long endTime = System.currentTimeMillis(); long totalTime = endTime - startTime; System.out .println("Execution time in milliseconds : " + totalTime); } } public static void backTrack(int sumPeople, int numRes, int idx) { if (numRes == K) { ans = Math.max(ans, sumPeople); return; // tranh time limit } for (int i = idx; i < M; i++) { int sumP = 0; QueueArray<Integer> queue = new QueueArray<Integer>(); for (int j = 0; j < N; j++) { if (!visitSoli[j] && isphucVu[i][j]) { sumP += numPeople[j]; visitSoli[j] = true; // queue.enQueue(j); } } backTrack(sumPeople + sumP, numRes + 1, i + 1); // while (!queue.isEmpty()) { // visitSoli[queue.deQueue()] = false; // } } } }
Editor is loading...