Untitled
unknown
plain_text
2 years ago
32 kB
12
Indexable
//Quan Ma~
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int N, M, ans, quan;
static int[][] map;
static int[][] mapDinh;
static int[][] danhSach;
static int[][] vis;
static int[] visDem;
static int[] dx = { -2, -1, 1, 2, 2, 1, -1, -2 };
static int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };
static MyQueue myQx = new MyQueue(100000);
static MyQueue myQy = new MyQueue(100000);
static MyQueue myQd = new MyQueue(100000);
public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
ans = 999999;
N = sc.nextInt();
M = sc.nextInt();
map = new int[N][M];
vis = new int[N][M];
danhSach = new int[N * M][2];
int a = 0, b = 0;
quan = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
if (map[i][j] == 3) {
danhSach[0][0] = i;
danhSach[0][1] = j;
}
if (map[i][j] == 1) {
quan++;
danhSach[quan][0] = i;
danhSach[quan][1] = j;
}
}
}
visDem = new int[quan + 1];
mapDinh = new int[quan + 1][quan + 1];
for (int i = 0; i < quan + 1; i++) {
bfs(danhSach[i][0], danhSach[i][1], i);
resetVis();
}
backTrack(0, 0, 0);
System.out.println("Case #" + tc);
System.out.println(ans);
// for (int i = 0; i < quan+1; i++) {
// for (int j = 0; j < quan+1; j++) {
// System.out.print(mapDinh[i][j]+" ");
// }
// System.out.println();
// }
}
}
static void backTrack(int a, int sum, int k) {
if (sum > ans) {
return;
}
if (k == quan) {
if (sum < ans) {
ans = sum;
}
return;
}
for (int i = 1; i < quan + 1; i++) {
if (visDem[i] == 0) {
visDem[i] = 1;
backTrack(i, sum + mapDinh[a][i], k + 1);
visDem[i] = 0;
}
}
}
static void bfs(int a, int b, int k) {
myQx.enQueue(a);
myQy.enQueue(b);
myQd.enQueue(0);
vis[a][b] = 1;
// if (map[a][b] == 1) {
// visDem[a][b] = 1;
// }
while (!myQx.isEmpty()) {
int x = myQx.deQueue();
int y = myQy.deQueue();
int d = myQd.deQueue();
for (int i = 0; i < 8; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r >= 0 && c >= 0 && r < N && c < M) {
if (map[r][c] == 0 && vis[r][c] == 0) {
myQx.enQueue(r);
myQy.enQueue(c);
myQd.enQueue(d + 1);
vis[r][c] = 1;
}
if (map[r][c] == 1 && vis[r][c] == 0) {
myQx.enQueue(r);
myQy.enQueue(c);
myQd.enQueue(d + 1);
vis[r][c] = 1;
int z = 0;
for (int j = 0; j < quan + 1; j++) {
if (danhSach[j][0] == r && danhSach[j][1] == c) {
z = j;
}
}
mapDinh[k][z] = d + 1;
}
}
}
}
}
static void resetVis() {
vis = new int[N][M];
myQx.resetQ();
myQy.resetQ();
myQd.resetQ();
}
}
class MyQueue {
private int front, rear, maxQueue;
private int[] map;
public MyQueue(int s) {
maxQueue = s;
map = new int[maxQueue];
front = rear = -1;
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
public boolean isFull() {
if (front == rear) {
return true;
}
return false;
}
public void resetQ() {
front = rear = -1;
}
public void enQueue(int inValue) {
rear++;
map[rear] = inValue;
}
public int deQueue() {
front++;
return map[front];
}
}
//Hugo Ban Dau
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int N, M, Hx, Hy, P, ans;
static int[][] map;
static int[][] vis;
static int[][] visDau;
static MyQueue myQ1 = new MyQueue(500000);
static MyQueue myQ2 = new MyQueue(500000);
static MyQueue myQ3 = new MyQueue(500000);
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
static int[][] ong = { { 1, 2, 5, 6 }, { 1, 3, 6, 7 }, { 1, 2, 4, 7 },
{ 1, 3, 4, 5 } };
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
ans = 0;
N = sc.nextInt();
M = sc.nextInt();
Hx = sc.nextInt();
Hy = sc.nextInt();
P = sc.nextInt();
map = new int[N][M];
vis = new int[N][M];
visDau = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
vis[i][j] = 0;
}
}
myQ1.enQueue(Hx);
myQ2.enQueue(Hy);
myQ3.enQueue(1);
vis[Hx][Hy] = 1;
bfs();
myQ1.resetQ();
myQ2.resetQ();
myQ3.resetQ();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visDau[i][j] == 1) {
ans++;
}
}
}
System.out.println("Case #" + tc);
System.out.println(ans + 1);
}
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("Total time: " + totalTime + " milliseconds");
}
static void bfs() {
while (!myQ1.isEmpty()) {
int x = myQ1.deQueue();
int y = myQ2.deQueue();
int d = myQ3.deQueue();
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r >= 0 && c >= 0 && r < N && c < M) {
if (map[x][y] == 1 && vis[r][c] == 0) {
if (map[r][c] == ong[i][0] || map[r][c] == ong[i][1]
|| map[r][c] == ong[i][2]
|| map[r][c] == ong[i][3]) {
myQ1.enQueue(r);
myQ2.enQueue(c);
myQ3.enQueue(d + 1);
vis[r][c] = 1;
if (d + 1 <= P) {
visDau[r][c] = 1;
}
}
}
if (map[x][y] == 2 && vis[r][c] == 0) {
if (i == 0 || i == 2) {
if (map[r][c] == ong[i][0]
|| map[r][c] == ong[i][1]
|| map[r][c] == ong[i][2]
|| map[r][c] == ong[i][3]) {
myQ1.enQueue(r);
myQ2.enQueue(c);
myQ3.enQueue(d + 1);
vis[r][c] = 1;
if (d + 1 <= P) {
visDau[r][c] = 1;
}
}
}
}
if (map[x][y] == 3 && vis[r][c] == 0) {
if (i == 1 || i == 3) {
if (map[r][c] == ong[i][0]
|| map[r][c] == ong[i][1]
|| map[r][c] == ong[i][2]
|| map[r][c] == ong[i][3]) {
myQ1.enQueue(r);
myQ2.enQueue(c);
myQ3.enQueue(d + 1);
vis[r][c] = 1;
if (d + 1 <= P) {
visDau[r][c] = 1;
}
}
}
}
if (map[x][y] == 4 && vis[r][c] == 0) {
if (i == 0 || i == 1) {
if (map[r][c] == ong[i][0]
|| map[r][c] == ong[i][1]
|| map[r][c] == ong[i][2]
|| map[r][c] == ong[i][3]) {
myQ1.enQueue(r);
myQ2.enQueue(c);
myQ3.enQueue(d + 1);
vis[r][c] = 1;
if (d + 1 <= P) {
visDau[r][c] = 1;
}
}
}
}
if (map[x][y] == 5 && vis[r][c] == 0) {
if (i == 1 || i == 2) {
if (map[r][c] == ong[i][0]
|| map[r][c] == ong[i][1]
|| map[r][c] == ong[i][2]
|| map[r][c] == ong[i][3]) {
myQ1.enQueue(r);
myQ2.enQueue(c);
myQ3.enQueue(d + 1);
vis[r][c] = 1;
if (d + 1 <= P) {
visDau[r][c] = 1;
}
}
}
}
if (map[x][y] == 6 && vis[r][c] == 0) {
if (i == 2 || i == 3) {
if (map[r][c] == ong[i][0]
|| map[r][c] == ong[i][1]
|| map[r][c] == ong[i][2]
|| map[r][c] == ong[i][3]) {
myQ1.enQueue(r);
myQ2.enQueue(c);
myQ3.enQueue(d + 1);
vis[r][c] = 1;
if (d + 1 <= P) {
visDau[r][c] = 1;
}
}
}
}
if (map[x][y] == 7 && vis[r][c] == 0) {
if (i == 0 || i == 3) {
if (map[r][c] == ong[i][0]
|| map[r][c] == ong[i][1]
|| map[r][c] == ong[i][2]
|| map[r][c] == ong[i][3]) {
myQ1.enQueue(r);
myQ2.enQueue(c);
myQ3.enQueue(d + 1);
vis[r][c] = 1;
if (d + 1 <= P) {
visDau[r][c] = 1;
}
}
}
}
}
}
}
}
}
class MyQueue {
private int front, rear, maxQueue;
private int[] Arrayqueue;
public MyQueue(int s) {
maxQueue = s;
Arrayqueue = new int[maxQueue];
front = rear = -1;
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
public boolean isFull() {
if (front == rear) {
return true;
}
return false;
}
public void resetQ() {
front = rear = -1;
}
public void enQueue(int invalue) {
rear++;
Arrayqueue[rear] = invalue;
}
public int deQueue() {
front++;
return Arrayqueue[front];
}
}
//Quang Cao
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int N, L1, L2, L3, P1, P2, P3, ans;
static int[][] danhSach;
static int[] ads;
static int[] diem;
static int[][] timeAds;
public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input1.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
ans = 0;
N = sc.nextInt();
ads = new int[3];
diem = new int[3];
danhSach = new int[N][3];
timeAds = new int[3][2];
ads[0] = sc.nextInt();
ads[1] = sc.nextInt();
ads[2] = sc.nextInt();
diem[0] = sc.nextInt();
diem[1] = sc.nextInt();
diem[2] = sc.nextInt();
int max = 0;
int min = 500;
for (int i = 0; i < N; i++) {
danhSach[i][0] = sc.nextInt();
danhSach[i][1] = sc.nextInt();
danhSach[i][2] = danhSach[i][0] + danhSach[i][1];
if (max < danhSach[i][2]) {
max = danhSach[i][2];
}
}
backTrack(0, max);
System.out.println("Case #" + tc);
System.out.println(ans);
}
}
static void backTrack(int k, int max) {
if (k == 3) {
if (set() > ans) {
ans = set();
}
return;
}
for (int i = 1; i <= max; i++) {
if (check(i, k)) {
timeAds[k][0] = i;
timeAds[k][1] = i + ads[k];
backTrack(k + 1, max);
timeAds[k][0] = 0;
timeAds[k][1] = 0;
}
}
}
private static int set() {
int rs = 0;
for (int i = 0; i < N; i++) {
int sum = 0;
for (int j = 0; j < 3; j++) {
int temp = 0;
if (danhSach[i][0] <= timeAds[j][0]
&& danhSach[i][2] >= timeAds[j][1]) {
temp = diem[j];
if (sum < temp) {
sum = temp;
}
}
}
rs += sum;
}
return rs;
}
static boolean check(int timeStart, int k) {
int timeEnd = timeStart + ads[k];
for (int i = 0; i < 3; i++) {
if (i != k && timeAds[i][0] != 0) {
if (timeStart > timeAds[i][0] && timeStart < timeAds[i][1]) {
return false;
}
if (timeStart <= timeAds[i][0] && timeEnd >= timeAds[i][1]) {
return false;
}
if (timeEnd > timeAds[i][0] && timeEnd < timeAds[i][1]) {
return false;
}
}
}
return true;
}
}
// Domino
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int N, M, ans;
static int[][] map;
static int[][] vis;
static int[][] arr;
static int[] dx = { 0, 1 };
static int[] dy = { 1, 0 };
public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input1.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
ans = 0;
map = new int[7][8];
vis = new int[7][8];
arr = new int[28][2];
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 8; j++) {
map[i][j] = sc.nextInt();
}
}
for (int i = 0; i < 28; i++) {
arr[i][0] = -1;
arr[i][1] = -1;
}
backTrack(0);
System.out.println("Case #" + tc);
System.out.println(ans);
}
}
static void backTrack(int quanCo) {
if (quanCo == 28) {
ans++;
return;
}
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 8; j++) {
if (vis[i][j] == 0) {
vis[i][j] = 1;
arr[quanCo][0] = map[i][j];
for (int k = 0; k < 2; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && y >= 0 && x < 7 && y < 8) {
if (vis[x][y] == 0) {
arr[quanCo][1] = map[x][y];
if (check(arr[quanCo][0], arr[quanCo][1])) {
vis[x][y] = 1;
backTrack(quanCo + 1);
arr[quanCo][1] = -1;
vis[x][y] = 0;
}
}
}
}
arr[quanCo][0] = -1;
vis[i][j] = 0;
return;
}
}
}
}
static boolean check(int arrX, int arrY) {
int count = 0;
for (int i = 0; i < 28; i++) {
if ((arrX == arr[i][0] && arrY == arr[i][1])
|| (arrX == arr[i][1] && arrY == arr[i][0])) {
count++;
}
}
if (count == 2) {
return false;
} else {
return true;
}
}
}
//TestCase
50
6 4 6 0 6 3 1 2
6 1 5 3 5 0 4 0
2 4 1 5 0 2 4 4
5 5 1 3 6 5 4 1
0 3 3 4 4 5 5 2
2 3 2 6 1 1 0 1
3 3 0 0 2 2 6 6
3 3 3 2 6 6 4 6
2 1 0 1 5 0 6 1
4 1 4 3 0 4 0 2
0 0 6 0 2 2 0 3
3 1 5 2 2 4 3 5
2 6 5 5 1 5 3 6
5 4 4 4 6 5 1 1
2 3 6 6 2 1 6 4
1 3 2 2 5 4 3 4
5 2 1 0 0 0 0 5
4 4 1 1 5 3 6 3
2 0 4 1 0 3 0 4
2 6 6 1 0 6 2 4
5 5 5 1 6 5 3 3
0 0 1 3 2 6 0 6
1 2 0 1 5 4 2 0
0 4 1 4 4 6 1 6
0 5 3 6 2 3 4 4
5 6 5 5 5 2 0 3
2 2 6 6 2 4 5 1
3 4 1 1 3 3 5 3
5 3 1 6 0 5 3 0
4 2 1 4 4 3 6 2
3 2 2 5 6 5 2 1
2 0 1 0 1 1 3 6
5 5 1 5 6 4 2 2
0 4 4 5 6 6 6 0
0 0 3 3 1 3 4 4
2 0 1 5 0 5 5 4
3 1 2 4 6 4 1 1
1 2 3 6 5 2 3 0
4 1 3 4 0 4 6 1
6 6 3 2 0 6 5 6
1 0 6 2 2 2 0 0
5 3 5 5 4 4 3 3
5 2 0 3 1 4 6 3
5 1 3 2 6 0 0 4
5 3 5 6 6 6 5 4
6 4 4 4 1 0 1 1
3 4 1 3 1 2 2 4
2 2 6 1 2 0 5 0
2 6 5 5 0 0 3 3
5 6 2 5 2 6 4 3
1 3 0 0 6 1 6 0
3 5 5 4 0 2 1 5
0 4 6 6 1 1 0 3
6 4 3 2 0 1 1 2
3 3 4 2 4 1 2 2
0 5 5 5 4 4 3 6
5 5 0 3 4 2 4 1
1 5 2 0 6 5 5 0
6 0 1 1 5 2 6 3
4 6 3 2 2 2 6 6
0 1 3 1 3 4 2 6
0 4 3 3 5 4 1 2
1 6 5 3 0 0 4 4
6 2 5 2 5 5 4 1
5 3 5 0 6 4 2 2
3 6 1 6 1 2 0 2
0 6 3 2 2 4 1 0
4 5 4 3 6 6 5 1
3 0 4 4 5 6 3 1
3 3 0 4 1 1 0 0
4 6 6 0 0 1 6 6
0 0 2 4 0 3 5 6
1 6 2 5 3 2 5 4
4 0 1 4 3 4 2 0
4 4 5 1 5 5 1 1
3 6 0 5 2 1 2 2
2 6 1 3 3 5 3 3
3 1 0 3 1 5 1 1
4 1 5 4 5 2 5 6
6 0 0 2 3 2 4 3
3 6 2 2 0 5 4 2
5 5 1 0 0 4 3 5
6 1 2 6 3 3 6 6
2 1 4 6 0 0 4 4
3 0 0 1 4 5 6 2
6 3 2 0 2 2 1 1
4 6 4 2 2 3 0 0
5 2 1 4 5 0 1 3
5 5 5 3 5 1 4 0
6 0 5 6 4 4 2 1
1 6 4 3 3 3 6 6
2 4 4 5 0 4 0 3
0 0 4 3 2 0 5 6
3 6 3 2 6 6 2 6
3 5 2 5 1 6 0 1
4 4 2 1 0 6 6 4
5 0 5 5 3 1 2 2
4 1 1 5 1 1 3 3
1 5 4 0 0 1 5 4
1 4 2 2 5 3 6 1
4 3 1 1 0 6 3 2
4 4 1 3 0 2 2 4
3 3 4 6 3 6 2 5
5 6 0 0 2 1 6 6
6 2 0 5 3 0 5 5
4 6 5 2 0 2 0 0
5 3 6 1 2 3 6 5
5 1 1 2 2 4 6 3
0 4 1 0 6 6 5 4
1 4 6 0 3 3 6 2
1 3 3 0 5 0 4 3
5 5 1 1 2 2 4 4
3 6 2 4 1 6 3 3
4 0 1 5 2 2 4 1
5 6 0 0 6 4 1 0
1 3 5 3 6 6 2 0
4 3 0 5 0 6 1 1
5 2 2 6 1 2 2 3
5 4 5 5 3 0 4 4
5 6 3 6 6 0 4 0
6 4 1 1 4 3 4 5
3 3 2 0 1 2 2 4
6 2 2 2 5 0 5 2
3 1 2 3 3 5 4 4
5 1 4 1 0 1 6 1
0 3 5 5 0 0 6 6
3 5 2 2 3 0 6 2
0 4 5 1 3 2 3 1
6 0 4 6 0 1 3 3
6 1 0 0 1 1 5 4
4 1 3 6 5 0 3 4
5 6 1 2 0 2 4 4
2 5 5 5 2 4 6 6
2 5 3 1 0 5 0 3
6 3 5 5 6 0 0 1
4 1 3 5 4 4 2 1
4 2 1 6 6 2 4 0
2 2 1 5 3 4 2 0
5 4 6 4 3 2 6 5
1 1 0 0 3 3 6 6
4 6 2 0 5 5 6 0
5 6 5 2 0 0 4 3
3 1 2 1 5 1 4 1
3 5 0 3 2 2 6 3
2 6 4 4 5 0 2 3
2 4 1 1 1 0 6 6
5 4 1 6 4 0 3 3
1 1 0 4 5 1 3 5
1 0 0 5 6 1 0 3
5 2 4 4 4 6 0 2
3 1 3 6 4 5 6 6
6 2 3 2 3 3 2 2
0 0 2 1 4 2 6 0
3 4 5 6 1 4 5 5
6 5 2 0 0 5 5 3
6 2 1 2 1 6 4 0
5 1 5 2 4 3 4 4
1 4 2 2 6 3 4 5
2 4 6 0 3 1 6 6
3 0 6 4 1 1 1 0
3 2 5 5 3 3 0 0
6 2 1 5 0 6 6 4
5 2 0 0 2 0 1 6
4 4 4 5 0 5 0 1
3 6 5 3 2 1 3 0
3 2 2 2 4 2 3 1
5 5 1 1 4 1 5 6
4 0 4 3 6 6 3 3
0 3 1 2 3 5 0 4
5 4 3 2 6 1 1 0
2 6 4 3 4 1 3 3
3 1 5 0 6 6 0 6
4 6 6 3 0 2 1 1
2 2 5 2 0 0 5 6
1 5 4 2 4 4 5 5
1 0 5 4 6 3 2 2
5 1 1 2 4 2 3 2
3 4 0 6 4 6 3 5
2 0 6 6 5 0 2 6
6 5 3 3 2 5 1 6
0 3 4 0 5 5 1 1
1 4 0 0 1 3 4 4
2 0 4 4 1 2 0 0
2 4 2 2 6 0 6 3
5 5 4 0 5 4 3 5
3 3 1 3 1 6 5 2
0 5 2 3 5 6 0 3
6 6 2 6 6 4 1 4
1 0 1 1 1 5 4 3
6 5 4 0 2 4 3 1
5 3 1 5 6 3 3 4
5 4 6 4 3 3 2 5
5 0 3 0 1 2 2 0
4 4 1 0 2 6 3 2
1 6 6 0 1 1 5 5
0 0 4 1 6 6 2 2
1 0 3 3 1 2 1 3
5 5 3 5 5 1 2 4
0 2 3 4 2 5 1 1
3 0 6 4 0 0 4 5
6 5 6 6 6 3 6 1
3 2 6 2 0 5 0 6
0 4 4 4 2 2 4 1
4 0 6 3 6 1 0 3
4 1 2 0 0 6 2 2
5 2 1 5 6 5 5 5
2 3 1 3 6 6 0 5
3 4 2 1 6 4 4 5
6 2 1 0 4 2 5 3
3 3 0 0 4 4 1 1
0 2 4 4 2 1 3 6
3 5 6 6 1 3 4 1
6 5 2 6 3 0 4 0
1 5 2 3 6 1 2 2
5 0 0 1 0 6 4 3
4 2 1 1 2 5 6 4
4 5 0 0 3 3 5 5
2 3 0 4 6 6 2 6
2 1 5 2 1 6 3 0
0 5 0 6 5 6 5 4
2 2 3 3 6 3 4 1
6 4 1 0 0 0 5 5
4 4 1 1 1 5 3 4
3 1 0 2 2 4 5 3
4 0 3 3 2 2 6 5
3 0 4 6 4 3 0 2
4 1 0 5 4 5 5 5
6 6 0 6 3 6 3 1
4 4 0 1 6 2 2 5
3 5 1 2 1 1 2 4
3 2 0 0 5 1 6 1
6 1 2 3 6 0 6 4
4 4 3 0 5 3 1 5
1 2 3 1 6 2 1 1
3 4 5 0 4 0 2 4
6 3 5 6 5 4 0 2
1 0 5 5 5 2 4 1
6 6 3 3 2 2 0 0
2 1 6 1 0 5 5 1
4 0 0 3 4 2 6 3
1 3 2 6 1 4 3 5
1 0 0 0 5 2 4 3
0 6 4 5 2 2 3 2
2 0 6 4 5 6 6 6
4 4 3 3 1 1 5 5
1 0 0 5 1 2 3 1
6 4 2 6 0 4 2 0
3 3 4 2 4 5 3 2
5 6 0 0 5 2 0 3
6 0 3 5 3 6 4 1
2 2 1 6 3 4 6 6
5 5 4 4 1 5 1 1
1 5 3 5 1 6 2 4
4 4 4 3 0 0 0 4
2 1 6 2 4 5 3 6
2 3 0 2 0 5 0 6
6 5 1 4 2 5 3 0
1 1 2 2 1 3 4 6
5 5 0 1 6 6 3 3
0 1 5 5 6 0 2 4
1 5 0 2 4 3 6 5
5 3 4 0 1 3 6 1
6 6 0 5 4 4 4 1
0 3 1 1 2 6 0 0
2 1 4 5 3 3 2 2
3 6 2 3 6 4 2 5
1 4 2 6 1 6 4 6
6 5 3 4 0 3 0 2
5 2 2 4 0 0 6 3
5 0 4 4 1 1 6 0
4 5 5 1 3 1 5 5
3 5 1 0 1 2 2 2
3 2 4 0 3 3 6 6
1 6 0 6 4 0 0 2
1 3 3 3 4 3 1 2
5 5 0 3 3 2 4 5
3 6 5 6 0 5 4 4
1 4 5 1 1 0 0 0
1 1 2 6 4 2 6 6
5 3 2 5 4 6 2 2
3 5 1 4 6 3 2 0
2 3 0 5 1 3 4 0
6 4 2 1 2 4 2 2
1 0 0 0 4 3 5 6
4 4 3 0 1 1 5 1
5 2 5 5 6 2 0 6
3 3 1 6 4 5 6 6
6 0 0 5 6 1 5 2
2 1 3 2 6 6 6 5
4 1 4 0 1 0 5 4
3 4 0 3 4 2 6 4
2 2 2 0 6 3 3 5
3 3 5 1 1 1 2 6
1 3 4 4 5 5 0 0
6 0 3 0 2 4 0 2
1 5 3 3 4 4 5 3
3 6 4 5 3 1 4 6
6 5 2 5 1 0 5 0
2 3 1 1 1 2 1 6
2 2 6 2 1 4 0 0
4 3 5 5 0 4 6 6
0 3 6 5 3 2 5 3
4 2 1 6 6 4 3 4
1 0 1 4 5 4 0 5
0 2 0 6 3 6 2 5
6 6 1 3 2 2 1 5
6 2 4 0 4 4 1 1
3 3 0 0 1 2 5 5
5 0 3 1 4 0 0 1
2 0 2 2 6 1 2 6
0 3 2 1 3 3 4 6
1 5 3 5 3 4 0 6
1 1 4 1 0 0 5 6
2 5 4 2 5 4 6 6
4 4 6 3 5 5 3 2
0 5 6 4 1 0 0 0
2 5 6 2 5 6 3 5
4 3 4 2 3 6 0 4
1 5 1 2 5 5 6 1
1 3 1 1 2 3 3 3
4 4 6 0 4 1 2 2
6 6 2 0 4 5 0 3
5 0 3 2 1 3 3 0
6 5 5 4 3 6 1 4
4 0 1 0 5 1 2 4
0 2 5 5 0 0 5 3
3 4 6 2 4 6 1 2
3 3 6 6 0 6 2 5
4 4 1 1 6 1 2 2
4 1 4 0 5 6 6 4
3 5 0 3 5 1 0 2
6 1 4 5 0 6 3 1
5 5 4 3 3 3 3 2
2 6 5 0 2 1 1 1
0 1 4 4 4 2 5 2
6 6 3 6 2 2 0 0
3 5 4 4 2 1 1 6
1 4 4 0 3 4 4 5
0 6 0 2 5 1 0 5
3 6 2 5 5 5 2 6
3 1 0 1 5 6 0 0
3 2 2 2 0 3 6 4
2 4 6 6 3 3 1 1
2 4 4 5 1 2 6 3
1 0 4 1 4 4 5 5
2 2 6 1 0 0 5 0
4 0 0 3 5 6 2 5
6 4 1 3 1 5 3 3
0 6 5 3 0 2 6 2
3 2 3 4 1 1 6 6
//Chi ong Nau nau Nau Nau Nau
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int M, N, ans, max, min, mid;
static int[][] map;
static int[] dxC = { 0, 1, 0, -1, -1, -1 };
static int[] dyC = { 1, 0, -1, -1, 0, 1 };
static int[] dxL = { 0, 1, 1, 1, 0, -1 };
static int[] dyL = { 1, 1, 0, -1, -1, 0 };
static int[][] vis;
public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input1.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
ans = 0;
N = sc.nextInt();
M = sc.nextInt();
map = new int[M][N];
vis = new int[M][N];
//min = 2000;
//max = 0;
for (int i = 0; i < M; 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];
// }
}
}
// mid = (max + min) / 2;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
// if (map[i][j] > mid) {
vis[i][j] = 1;
backTrack(i, j, map[i][j], 1);
backTrack1(i, j, map[i][j], 1);
// if (j % 2 == 0) {
// backTrack1(i, j, map[i][j], 1);
// } else {
// backTrack2(i, j, map[i][j], 1);
// }
vis[i][j] = 0;
// }
}
}
System.out.println("Case #" + tc);
System.out.println(ans * ans);
}
}
// static void backTrack1(int a, int b, int sum, int k) {
//
// if (k == 4) {
// if (sum > ans) {
// ans = sum;
// }
// return;
// }
// for (int i = 0; i < 6; i++) {
// int x = a + dxC[i];
// int y = b + dyC[i];
// if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
// vis[x][y] = 1;
// backTrack1(a, b, sum + map[x][y], k + 1);
// vis[x][y] = 0;
// }
// }
//
// }
//
// static void backTrack2(int a, int b, int sum, int k) {
//
// if (k == 4) {
// if (sum > ans) {
// ans = sum;
// }
// return;
// }
// for (int i = 0; i < 6; i++) {
// int x = a + dxL[i];
// int y = b + dyL[i];
// if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
// vis[x][y] = 1;
// backTrack2(a, b, sum + map[x][y], k + 1);
// vis[x][y] = 0;
// }
// }
//
// }
static void backTrack(int a, int b, int sum, int k) {
if (k == 4) {
if (sum > ans) {
ans = sum;
}
return;
}
for (int i = 0; i < 6; i++) {
if (b % 2 == 0) {
int x = a + dxC[i];
int y = b + dyC[i];
if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
vis[x][y] = 1;
backTrack(x, y, sum + map[x][y], k + 1);
vis[x][y] = 0;
}
}
if (b % 2 != 0) {
int x = a + dxL[i];
int y = b + dyL[i];
if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
vis[x][y] = 1;
backTrack(x, y, sum + map[x][y], k + 1);
vis[x][y] = 0;
}
}
}
}
static void backTrack1(int a, int b, int sum, int k) {
if (k == 4) {
if (sum > ans) {
ans = sum;
}
return;
}
for (int i = 0; i < 6; i++) {
if (b % 2 == 0) {
int x = a + dxC[i];
int y = b + dyC[i];
if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
vis[x][y] = 1;
backTrack1(a, b, sum + map[x][y], k + 1);
vis[x][y] = 0;
}
}
if (b % 2 != 0) {
int x = a + dxL[i];
int y = b + dyL[i];
if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
vis[x][y] = 1;
backTrack1(a, b, sum + map[x][y], k + 1);
vis[x][y] = 0;
}
}
}
}
}
//Hugo Ve Nha
Hugo đang trền đường về nhà và cần đi qua 1 đoạn đường B.
Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng Hugo có 3 cách lựa chọn.
1. Pass
Trả số tiền quy định ở cổng đó để được đi qua
2. Hire
Trả gấp đôi số tiền ở cổng đó để thuê số binh sĩ gộp vào đoàn quân của mình
3. battle
Điều kiện để đánh nhau là số quân của Hugo >= số lượng lính tại cổng đó. Có các lưu ý:
+ Hugo k được tính vào số lượng của quân
+ Mỗi người lính chỉ tham gia được vào tối đa 3 trận đánh. Sau 3 trận đánh nếu đi nhóm binh sĩ đó còn sống thì cũng giải tán.
+ Mỗi trận đánh thì tất cả số binh sĩ đều tham gia.
+ Đánh nhau chết theo tỉ lệ 1: 1. Ai tham gia trước sẽ bị chết trước
Input:
Dòng đầu tiên là số lượng trường hợp thử nghiệm
Mỗi trường hợp thử nghiệm sẽ có
Dòng đầu tiên chứa số lượng cổng N
N dòng tiếp theo chứa 2 số là số binh lính và chi phí tại mỗi cổng
Output: In ra chi phí nhỏ nhất Hugo có thể đi qua đoạn đường B
Điều kiện input: số cổng <=20
- 2 <=Số lính và chi phí đi qua <=1000
VD:
Input
2
7
10 100
70 5
80 15
20 60
50 90
30 80
10 10
9
600 800
300 400
300 400
1000 400
300 600
100 300
600 300
600 500
1000 300
Output:
#1 150
#2 3000
Giải thích
1 2 3 4 5 6 7
Số binh sĩ 10 70 80 20 50 30 10
Chi phí 100 5 15 60 90 80 10
Có thể tính chi phí đi nhỏ nhất
1 2 3 4 5 6 7
Số binh sĩ 10 70 80 20 50 30 10
Chi phí 100 5 15 60 90 80 10
Chọn Pass Hire Hire Battle Battle Battle Pass
Chi phí 100 110 140 150
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int N, ans;
static int[][] map;
static int[][] vis;
static int L1, L2, L3;
public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
ans = 99999999;
N = sc.nextInt();
map = new int[N][2];
L1 = 0;
L2 = 0;
L3 = 0;
for (int i = 0; i < N; i++) {
map[i][0] = sc.nextInt();
map[i][1] = sc.nextInt();
}
backTrack(0, 0, 0);
System.out.println("Case #" + tc);
System.out.println(ans);
}
}
static void backTrack(int k, int sum, int linh) {
if (ans < sum) {
return;
}
if (k == N) {
if (ans > sum) {
ans = sum;
}
return;
}
for (int i = 0; i < 3; i++) {
if (i == 0) {
backTrack(k + 1, sum + map[k][1], linh);
}
if (i == 1) {
L1 += map[k][0];
backTrack(k + 1, sum + (map[k][1] * 2), linh + L1);
L1 -= map[k][0];
}
if (i == 2) {
if (linh >= map[k][0]) {
if (map[k][0] <= L3) {
int linhDanhXong = L3;
L3 = L2;
L2 = L1;
L1 = 0;
backTrack(k + 1, sum, linh - linhDanhXong);
L1 = L2;
L2 = L3;
L3 = linhDanhXong;
} else {
int conLai = map[k][0] - L3;
if (conLai <= L2) {
int linh3DanhXong = L3;
L3 = L2 - conLai;
L2 = L1;
L1 = 0;
backTrack(k + 1, sum, linh - map[k][0]);
L1 = L2;
L2 = L3 + conLai;
L3 = linh3DanhXong;
} else {
int conLaiCuoi = conLai - L2;
if (conLaiCuoi <= L1) {
int linh3DanhXong = L3;
int linh2DanhXong = L2;
L3 = 0;
L2 = L1 - conLaiCuoi;
L1 = 0;
backTrack(k + 1, sum, linh - map[k][0]);
L1 = L2 + conLaiCuoi;
L2 = linh2DanhXong;
L3 = linh3DanhXong;
} else {
return;
}
}
}
}
}
}
}
}
//Quan Tuong
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int n, m, q, p, s, t, ans;
static int[][] map;
static int[] dx = { -1, 1, 1, -1 };
static int[] dy = { 1, 1, -1, -1 };
static MyQueue myQx = new MyQueue(500000);
static MyQueue myQy = new MyQueue(500000);
public static void main(String[] args) {
try {
System.setIn(new FileInputStream("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
ans = 0;
n = sc.nextInt();
m = sc.nextInt();
p = sc.nextInt();
q = sc.nextInt();
s = sc.nextInt();
t = sc.nextInt();
map = new int[n + 1][n + 1];
myQx.resetQ();
myQy.resetQ();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
map[i][j] = -1;
}
}
// map[s][t] = -1;
for (int i = 1; i <= m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
map[a][b] = -2;
}
bfs();
// System.out.println("Case #" + tc);
System.out.println(map[s][t]);
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// System.out.print(map[i][j] + " ");
// }
// System.out.println();
// }
}
}
static void bfs() {
myQx.enQueue(p);
myQy.enQueue(q);
map[p][q] = 0;
while (!myQx.isEmpty()) {
int x = myQx.deQueue();
int y = myQy.deQueue();
for (int i = 0; i < 4; i++) {
int r = x;
int c = y;
while (true) {
r += dx[i];
c += dy[i];
if (r < 1 || c < 1 || r > n || c > n || map[r][c] == -2) {
break;
}
else if (map[r][c] == -1 || map[r][c] > map[x][y]) {
map[r][c] = map[x][y] + 1;
myQx.enQueue(r);
myQy.enQueue(c);
}
}
}
}
}
}
// int r1 = r + dx[i];
// int c1 = c + dy[i];
// while(r1 >= 0 && c1 >= 0 && r1 < n && c1 < n && map[r1][c1]!=
// -2){
// vis[r1][c1] = vis[r][c] + 1;
// if(r1 == s && c1 == t){
// ans = vis[r][c];
// return;
// }
// myQx.enQueue(r);
// myQy.enQueue(c);
// r1 += dx[i];
// c1 += dy[i];
// }
class MyQueue {
private int front, rear, maxQueue;
private int[] map;
public MyQueue(int s) {
maxQueue = s;
map = new int[maxQueue];
front = rear = -1;
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
public boolean isFull() {
if (front == rear) {
return true;
}
return false;
}
public void resetQ() {
front = rear = -1;
}
public void enQueue(int inValue) {
rear++;
map[rear] = inValue;
}
public int deQueue() {
front++;
return map[front];
}
}
//Battle City
//
Editor is loading...