Untitled

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