时间戳

首页 > 解决方案 > 是否有任何有效的微优化来找到唯一网格路径的数量？

java - 是否有任何有效的微优化来找到唯一网格路径的数量？

问题描述

我正在尝试解决这个 CSES 问题：Grid Paths。你得到一个长度为 48 的字符串，你必须找到路径的数量，这样你才能遍历所有网格并最终到达左下角。

我相信我已经尽我所能修剪了搜索，根据这本书：CP手册（在修剪搜索类别中查看），此类问题的最佳优化是防止您的路径关闭自己，我已经实现了这一点。这个特定问题的时间限制很紧，虽然我已经基本解决了这个问题，但我仍然失败了 1-2 个测试用例，因为我的解决方案大约需要 1.01 秒，而不是低于 1 秒的时间限制。

最后，我只是想知道是否有任何很酷的微优化可以用来稍微提高我的 java 代码的速度，这样我实际上可以通过这个问题的所有测试用例。

import java.io.*;

public class GridPaths {
    public static class FastIO {
        InputStream dis;
        byte[] buffer = new byte[1 << 17];
        int pointer = 0;

        public FastIO(String fileName) throws Exception {
            dis = new FileInputStream(fileName);
        }

        public FastIO(InputStream is) {
            dis = is;
        }

        int nextInt() throws Exception {
            int ret = 0;
            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }
            while (b >= '0' && b <= '9') {
                ret = 10 * ret + b - '0';
                b = nextByte();
            }
            return (negative) ? -ret : ret;
        }

        long nextLong() throws Exception {
            long ret = 0;
            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }
            while (b >= '0' && b <= '9') {
                ret = 10 * ret + b - '0';
                b = nextByte();
            }
            return (negative) ? -ret : ret;
        }

        Integer[] readArray(int n) throws Exception {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        byte nextByte() throws Exception {
            if (pointer == buffer.length) {
                dis.read(buffer, 0, buffer.length);
                pointer = 0;
            }
            return buffer[pointer++];
        }

        String next() throws Exception {
            StringBuilder ret = new StringBuilder();
            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            while (b > ' ') {
                ret.appendCodePoint(b);
                b = nextByte();
            }
            return ret.toString();
        }
    }

    static char[] board;
    static boolean[][] visited = new boolean[7][7];
    static int ans = 0;

    public static boolean works(int i, int j) {
        //makes sure that current spot is on the 7x7 grid and is not visited
        return (i >= 0 && i<=6 && j>=0 && j<=6 && !visited[i][j]);
    }
    public static void solve(int i, int j, int steps) {
        if (i == 6 && j == 0) {
            if (steps == 48) ans++; //all spots of the grid have to be visited in order to be counted as part of the answer
            return;
        }
        visited[i][j] = true;
        //you are given ? characters in the input string, and those mean that you have to try out all 4 combinations (U,D,L,R)
        if (board[steps] == '?' || board[steps] == 'L') {
            //second condition of the second if statement checks if the spot directly ahead of the current spot is blocked, and if it is, the left and right spots cannot both be unvisited or else you will not continue searching 
            if (works(i,j-1) && !(!works(i,j-2) && works(i+1,j-1) && works(i-1,j-1))) {
                solve(i, j - 1, steps + 1);
            }
        }
        if (board[steps] == '?' || board[steps] == 'R') {
            if (works(i,j+1) && !(!works(i,j+2) && works(i+1,j+1) && works(i-1,j+1))) {
                solve(i, j + 1, steps + 1);
            }
        }
        if (board[steps] == '?' || board[steps] == 'U') {
            if (works(i-1,j) && !(!works(i-2,j) && works(i-1,j+1) && works(i-1,j-1))) {
                solve(i - 1, j, steps + 1);
            }
        }
        if (board[steps] == '?' || board[steps] == 'D') {
            if (works(i+1,j) && !(!works(i+2,j) && works(i+1,j+1) && works(i+1,j-1))) {
                solve(i + 1, j, steps + 1);
            }
        }
        visited[i][j] = false;

    }
    public static void main(String[] args) throws Exception {
        FastIO in = new FastIO(System.in);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        board = in.next().toCharArray();
        solve(0,0,0);
        out.println(ans);

        out.close();
    }

}

注意：我已经在使用最快的（如果不是最快的）Java 接收输入的方法之一，所以我不相信我可以真正改进它。

标签： javamicro-optimization

解决方案

我一直在玩这个。除了使用标准机制来读取输入文件（我在评论中建议）之外，您还可以通过做两件事在搜索 alg 本身中获得一点时间：

  1. 将案件board[steps] == '?'与其他案件分开。所以先检查一下board[steps] == '?'，然后在这种情况下尝试所有四个方向。否则（对于 的else情况if (board[steps] == '?')，只需检查 U/D/L/R。由于对于大多数步骤，字符将是“？”，因此您大部分时间都不必进行 U/D/L/R 测试。

  2. 用 ,查找要测试的字符一次，c = board[steps]然后c在每个测试中使用而不是board[steps]。

做这两件事似乎节省了大约 5%。我用System.currentTimeMillis(). 我知道有更准确的计时方法，但这足以看到明显的改进，即使时间跳跃了相当多的试验。在每种情况下，我见过的最好的结果是最初编写的 100 次迭代的 3600 毫秒与改进后的 3400 毫秒。

我的猜测是，这主要是第一个重要的变化。我希望编译器已经在做第二个，但我没有独立尝试这两个优化。

推荐阅读