Untitled
unknown
plain_text
a year ago
8.7 kB
0
Indexable
package OnLuyen;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Netharax {
static int n, m, y_start, max;
static int x0, x1, x2, x3, x4, x5;
static int[][] matrix;
static int[] dx = { -1, -2, -2, -1 };
static int[] dy = { -2, -1, 1, 2 };
static int[][] visit;
static void input(Scanner sc) {
n = sc.nextInt();
m = sc.nextInt();
y_start = sc.nextInt();
matrix = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
matrix[i][j] = sc.nextInt();
}
}
}
static int isOutOfCheck(int x, int y) {
if (x < 1 || x > n || y < 1 || y > m) {
return 1;
}
return 0;
}
static void backTrack(int x, int y, int _0, int _1, int _2, int _3, int _4, int _5) {
if (matrix[x][y] == 6) {
int sum = 0;
sum += _0 * 5;
sum += _1 / 6 * 150;
sum += (_1 % 6) / 3 * 50;
sum += (_1 % 6) % 3 * 10;
sum += _2 / 2 * 100;
sum += _2 % 2 * 30;
if (_3 == 1) {
sum += 20;
} else if (_3 == 2) {
sum += 50;
} else if (_3 == 3) {
sum += 100;
} else if (_3 == 4) {
sum += 200;
} else if (_3 >= 5) {
sum += 500;
}
sum += _4 * 1000;
sum += 1;
if (max < sum) {
x0 = _0;
x1 = _1;
x2 = _2;
x3 = _3;
x4 = _4;
x5 = _5;
max = sum;
}
return;
}
int X, Y;
for (int i = 0; i < 4; i++) {
X = x + dx[i];
Y = y + dy[i];
if (isOutOfCheck(X, Y) == 0 && visit[X][Y] == 0) {
visit[X][Y] = 1;
if (matrix[X][Y] == 0) {
backTrack(X, Y, _0 + 1, _1, _2, _3, _4, _5);
} else if (matrix[X][Y] == 1) {
backTrack(X, Y, _0, _1 + 1, _2, _3, _4, _5);
} else if (matrix[X][Y] == 2) {
backTrack(X, Y, _0, _1, _2 + 1, _3, _4, _5);
} else if (matrix[X][Y] == 3) {
backTrack(X, Y, _0, _1, _2, _3 + 1, _4, _5);
} else if (matrix[X][Y] == 5) {
backTrack(X, Y, _0, _1, _2, _3, _4, _5 + 1);
} else if (matrix[X][Y] == 4) {
if (_5 > 0) {
backTrack(X, Y, _0, _1, _2, _3, _4 + 1, _5 - 1);
}
} else {
backTrack(X, Y, _0, _1, _2, _3, _4, _5);
}
visit[X][Y] = 0;
}
}
}
static void solve(int tc) {
max = -1;
visit = new int[n + 1][m + 1];
visit[n][y_start] = 1;
if (matrix[n][y_start] == 0) {
backTrack(n, y_start, 1, 0, 0, 0, 0, 0);
} else if (matrix[n][y_start] == 1) {
backTrack(n, y_start, 0, 1, 0, 0, 0, 0);
} else if (matrix[n][y_start] == 2) {
backTrack(n, y_start, 0, 0, 1, 0, 0, 0);
} else if (matrix[n][y_start] == 3) {
backTrack(n, y_start, 0, 0, 0, 1, 0, 0);
} else if (matrix[n][y_start] == 5) {
backTrack(n, y_start, 0, 0, 0, 0, 0, 1);
}
// System.out.println(x0 + " " + x1 + " " + x2 + " " + x3 + " " + x4 + " " + x5);
System.out.println("Case #" + tc);
System.out.println(max);
}
public static void main(String[] args) throws FileNotFoundException {
long st = System.currentTimeMillis();
System.setIn(new FileInputStream("Netharax.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 0; i < T; i++) {
input(sc);
solve(i + 1);
}
long end = System.currentTimeMillis();
System.out.println("Time: " + (double) (end - st) / 1000);
}
}
//11
//15 8 4
//6 6 6 6 6 6 6 6
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//15 8 4
//6 6 6 6 6 6 6 6
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 0 1 0 0 0
//0 0 4 0 0 0 0 0
//0 0 0 0 0 0 0 0
//0 0 0 5 0 0 0 0
//0 4 0 0 0 0 0 0
//0 0 0 3 0 0 0 0
//0 2 0 0 0 0 0 0
//0 0 0 1 0 0 0 0
//20 10 4
//6 6 6 6 6 6 6 6 6 6
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 3 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//4 4 4 3 4 4 4 4 4 4
//4 3 4 4 3 4 4 4 4 4
//4 4 3 4 4 4 4 4 4 4
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 5 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//20 10 4
//6 6 6 6 6 6 6 6 6 6
//4 1 0 3 3 0 4 3 0 0
//2 1 1 2 3 0 0 3 4 3
//3 2 1 2 4 3 3 4 0 4
//3 4 4 4 3 2 2 3 3 1
//2 3 1 3 1 0 3 4 2 0
//0 1 4 2 3 3 4 4 4 2
//1 2 2 0 3 1 2 2 2 1
//0 0 1 0 1 0 0 2 3 0
//1 2 2 0 4 4 4 3 4 0
//3 1 0 0 1 2 1 2 0 0
//0 3 2 1 1 2 3 2 1 1
//1 3 0 0 1 2 0 4 4 4
//4 0 4 4 4 3 0 0 0 2
//2 2 4 3 1 0 1 0 4 0
//2 2 1 4 0 4 1 0 3 3
//0 3 4 1 3 2 1 3 1 1
//4 2 2 2 2 1 2 4 2 4
//3 4 0 0 2 3 0 2 3 4
//1 2 4 3 4 0 3 0 0 0
//20 10 7
//6 6 6 6 6 6 6 6 6 6
//0 0 0 1 1 3 4 2 2 1
//3 2 2 1 3 3 2 4 3 1
//1 2 0 4 0 1 4 4 1 4
//1 2 1 2 3 3 1 0 4 3
//1 4 4 4 2 1 0 1 3 2
//4 0 1 1 1 2 0 2 3 0
//1 2 4 4 2 2 4 1 0 1
//3 1 2 3 0 0 3 0 1 3
//2 0 0 0 4 2 1 1 2 4
//1 4 4 1 3 3 1 1 3 0
//1 2 3 4 1 4 2 0 4 4
//1 4 4 4 1 3 2 3 2 2
//4 3 0 1 4 1 3 3 0 1
//1 2 1 3 1 1 3 4 0 1
//0 3 0 4 0 2 0 2 2 4
//1 2 3 3 2 4 4 4 1 1
//1 4 4 0 0 4 3 0 0 4
//4 4 4 1 2 0 4 3 2 0
//3 2 0 1 0 0 3 3 4 2
//20 10 4
//6 6 6 6 6 6 6 6 6 6
//4 1 0 3 3 0 4 3 0 0
//2 1 1 2 3 0 0 3 4 3
//3 2 1 2 4 3 3 4 0 4
//3 4 4 4 3 2 2 3 3 1
//2 3 1 3 1 0 3 4 2 0
//0 1 4 2 3 3 4 4 4 2
//1 2 2 0 5 1 2 2 2 1
//0 0 1 0 1 0 0 2 3 0
//1 2 2 0 4 4 4 3 4 0
//3 1 0 0 1 2 1 2 0 0
//0 3 2 1 1 2 3 2 1 1
//1 3 0 0 1 2 0 4 4 4
//4 0 4 4 4 3 0 0 0 2
//2 2 4 3 1 0 1 0 4 0
//2 2 1 4 0 4 1 0 3 3
//0 3 4 1 3 2 1 3 1 1
//4 2 2 2 2 1 2 4 2 4
//3 4 0 0 2 3 0 2 3 4
//1 2 4 3 4 0 3 0 0 0
//20 10 7
//6 6 6 6 6 6 6 6 6 6
//0 0 0 1 1 3 4 2 2 1
//3 2 2 1 3 3 2 4 3 1
//1 2 0 4 0 1 4 4 1 4
//1 2 1 2 3 3 1 0 4 3
//1 4 4 4 2 1 0 1 3 2
//4 0 1 1 1 2 0 2 3 0
//1 2 4 4 2 2 4 1 0 1
//3 1 5 3 0 0 3 0 1 3
//2 0 0 0 4 2 1 1 2 4
//1 4 4 1 3 3 1 1 3 0
//1 2 3 4 1 4 2 0 4 4
//1 4 4 4 1 3 2 3 2 2
//4 3 0 1 4 1 3 3 0 1
//1 2 1 3 1 1 3 4 0 1
//0 3 0 4 0 2 0 2 2 4
//1 2 3 3 2 4 4 4 1 1
//1 4 4 0 0 4 3 0 0 4
//4 4 4 1 2 0 4 3 2 0
//3 2 0 1 0 0 3 3 4 2
//20 10 4
//6 6 6 6 6 6 6 6 6 6
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//1 1 1 1 1 1 1 1 1 1
//20 10 4
//6 6 6 6 6 6 6 6 6 6
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 4 2 2 2 4 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//20 10 4
//6 6 6 6 6 6 6 6 6 6
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//4 4 4 4 4 4 4 4 4 4
//4 4 4 4 4 4 4 4 4 4
//4 4 4 4 4 4 4 4 4 4
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//2 2 2 2 2 5 2 2 2 2
//2 2 2 2 2 2 2 2 2 2
//20 10 4
//6 6 6 6 6 6 6 6 6 6
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//20 10 4
//6 6 6 6 6 6 6 6 6 6
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//3 3 3 3 3 3 3 3 3 3
//output
//1: 71
//1106
//1751
//936
//986
//1821
//1761
//461
//901
//1731