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

        }


    }


} 

#阿里巴巴##笔试题目#
全部评论
点赞 回复 分享
发布于 2020-07-31 21:09
点赞 回复 分享
发布于 2020-07-31 20:55

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
4
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务