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

Question

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

我相信我已尽我所能修剪搜索，正如本书所述：CP Handbook（查看修剪搜索类别），此类问题的最佳优化是防止你的道路关闭你自己，我已经实现了这一点。这个特定问题的时间限制很紧，虽然我已经基本解决了这个问题，但我仍然有 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 中接收输入的最快（如果不是最快的话）方法之一，所以我认为我实际上无法改进它。

Answer 1

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

将案例 board[steps] == '?' 与其他案例分开。所以首先检查 board[steps] == '?'，然后在这种情况下尝试所有四个方向。否则（if (board[steps] == '?') 的 else 情况，只需检查 U/D/L/R。因为对于大多数步骤，字符将是 '?'，您不必进行 U/D/L/R 测试大多数时候。
查找要测试的字符一次，用c = board[steps]，然后在每次测试中使用c而不是board[steps]。

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

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

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

Are there any efficient micro-optimizations to find the number of unique grid paths?

java

micro-optimization