华为笔试第三题,回溯法,不知哪里有问题。。

用回溯法,当前的点为(curX,curY),每次根据条件搜索上下左右,如果当前的点等于(z,w),那么全局count++。

But,每次都是45.45%,不知道哪里做错了,大家帮忙看看。

public class Main {
    static int count = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] path = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                path[i][j] = scanner.nextInt();
            }
        }

        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int z = scanner.nextInt();
        int w = scanner.nextInt();
        back(path,x,y,z,w);
        System.out.println(count%(int)(Math.pow(10,9)));
    }



    public static void back(int[][] path, int cuX, int cuY, int z, int w) {
        if (cuX == z && cuY == w) {
            count++;
            return;
        }

        //上
        if (cuX - 1 >= 0) {
            int nextX = cuX - 1;
            if (path[cuX][cuY] < path[nextX][cuY]) {
                back(path, nextX, cuY, z, w);
            }
        }

        //下
        if (cuX + 1 < path.length) {
            int nextX = cuX + 1;
            if (path[cuX][cuY] < path[nextX][cuY]) {
                back(path, nextX, cuY, z, w);
            }
        }

        //左
        if (cuY - 1 >= 0) {
            int nextY = cuY - 1;
            if (path[cuX][cuY] < path[cuX][nextY]) {
                back(path, cuX, nextY, z, w);
            }
        }

        //右
        if (cuY + 1 < path[0].length) {
            int nextY = cuY + 1;
            if (path[cuX][cuY] < path[cuX][nextY]) {
                back(path, cuX, nextY, z, w);
            }
        }
    }
}
#华为##笔试题目#
全部评论
**咱俩代码一毛一样😀,最后时间来不及了忘了最后取模了
点赞 回复 分享
发布于 2019-04-11 09:13
总体思路差不多 但是加上带记忆的回溯 可以ac
点赞 回复 分享
发布于 2019-04-11 08:26
同Python 同样的做法 同样的45.45😂
点赞 回复 分享
发布于 2019-04-10 23:20
45.45%应该是11个用例过了5个,个人感觉这道题一般思路都是递归调用吧,这样做复杂度是指数级别的,当输入规模较大时,应该是不能在规定时间跑出来的😂
点赞 回复 分享
发布于 2019-04-10 23:10

相关推荐

07-02 10:44
门头沟学院 C++
码农索隆:太实诚了,告诉hr,你能实习至少6个月
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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