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; } } } }