7.31 阿里笔试 题解
a了第一道，第二道忘记点要设置visit标记了，没a出来，之后写出来了，太菜了😥。
第一题，二项式定理，要用到快速幂，注意要用long表示，因为会溢出。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int c = (int) Math.pow(10, 9) + 7;
long res = pow(1 + m, n, c);
System.out.println(res);
}
public static long pow(long a, long b, long c) {
long ans = 1;
long base = a % c;
while (b != 0) {
if ((b & 1) == 1) {
ans = ans * base % c;
}
base = base * base % c;
b = b >> 1;
}
return ans;
}
} 第二题，dfs，注意判断条件 import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
int n, m, q;
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
q = scanner.nextInt();
char[][] map = new char[n][m];
for (int i = 0; i < n; i++) {
String str = scanner.next();
for (int j = 0; j < m; j++) {
map[i][j] = str.charAt(j);
}
}
while (q-- > 0) {
int bx = scanner.nextInt() - 1;
int by = scanner.nextInt() - 1;
int ex = scanner.nextInt() - 1;
int ey = scanner.nextInt() - 1;
res = Integer.MAX_VALUE;
int[][] visit = new int[n][m];
visit[bx][by] = 1;
dfs(map, visit, bx, by, ex, ey, map[bx][by], 0, n, m);
System.out.println(res);
}
}
static int res;
public static void dfs(char[][] map, int[][] visit, int bx, int by, int ex, int ey, char pre, int cost, int n, int m) {
int step;
if (bx == ex && by == ey) {
res = Math.min(res, cost);
return;
}
if (pre == 'C') {
if (bx + 1 < n && visit[bx + 1][by] == 0) {
if (map[bx + 1][by] == 'C') {
step = 3;
} else {
step = 5;
}
pre = map[bx + 1][by];
visit[bx + 1][by] = 1;
dfs(map, visit, bx + 1, by, ex, ey, pre, cost + step, n, m);
visit[bx + 1][by] = 0;
}
if (bx - 1 >= 0 && visit[bx - 1][by] == 0) {
if (map[bx - 1][by] == 'C') {
step = 3;
} else {
step = 5;
}
pre = map[bx - 1][by];
visit[bx - 1][by] = 1;
dfs(map, visit, bx - 1, by, ex, ey, pre, cost + step, n, m);
visit[bx - 1][by] = 0;
}
if (by + 1 < m && visit[bx][by + 1] == 0) {
if (map[bx][by + 1] == 'C') {
step = 3;
} else {
step = 5;
}
pre = map[bx][by + 1];
visit[bx][by + 1] = 1;
dfs(map, visit, bx, by + 1, ex, ey, pre, cost + step, n, m);
visit[bx][by + 1] = 0;
}
if (by - 1 >= 0 && visit[bx][by - 1] == 0) {
if (map[bx][by - 1] == 'C') {
step = 3;
} else {
step = 5;
}
pre = map[bx][by - 1];
visit[bx][by - 1] = 1;
dfs(map, visit, bx, by - 1, ex, ey, pre, cost + step, n, m);
visit[bx][by - 1] = 0;
}
} else {
if (bx + 1 < n && visit[bx + 1][by] == 0) {
if (map[bx + 1][by] == 'C') {
step = 5;
} else {
step = 2;
}
pre = map[bx + 1][by];
visit[bx + 1][by] = 1;
dfs(map, visit, bx + 1, by, ex, ey, pre, cost + step, n, m);
visit[bx + 1][by] = 0;
}
if (bx - 1 >= 0 && visit[bx - 1][by] == 0) {
if (map[bx - 1][by] == 'C') {
step = 5;
} else {
step = 2;
}
pre = map[bx - 1][by];
visit[bx - 1][by] = 1;
dfs(map, visit, bx - 1, by, ex, ey, pre, cost + step, n, m);
visit[bx - 1][by] = 0;
}
if (by + 1 < m && visit[bx][by + 1] == 0) {
if (map[bx][by + 1] == 'C') {
step = 5;
} else {
step = 2;
}
pre = map[bx][by + 1];
visit[bx][by + 1] = 1;
dfs(map, visit, bx, by + 1, ex, ey, pre, cost + step, n, m);
visit[bx][by + 1] = 0;
}
if (by - 1 >= 0 && visit[bx][by - 1] == 0) {
if (map[bx][by - 1] == 'C') {
step = 5;
} else {
step = 2;
}
pre = map[bx][by - 1];
visit[bx][by - 1] = 1;
dfs(map, visit, bx, by - 1, ex, ey, pre, cost + step, n, m);
visit[bx][by - 1] = 0;
}
}
}
} 
投递百融云创等公司10个岗位