题解 | #走方格的方案数#

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static int total = 0;
    private static int n = 0;
    private static int m = 0;


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        while (in.hasNextInt()) { // 注意 while 处理多个 case
            if(n == 0){
                n = in.nextInt();
            } else if(m == 0) {
                m = in.nextInt();
            }
        }

        findAllRoute();

    }

    private static boolean end(int i, int j) {
        return i == n && j == m;
    }


    private static void findAllRoute() {


        Node1 root =  new Node1();
        root.num = 0;
        root.i = 0;
        root.j = 0;
        root.endNode = false;
        try {
            hasNext(root);
        } catch (Exception e) {
            e.printStackTrace();
        }

        System.out.println(total);
    }


    private static void hasNext(Node1 node) {

        if (node.endNode) {
            return;
        }

        if (node.i < n) {
            Node1 nextRight =  new Node1();
            nextRight.num = node.num + 1;
            nextRight.i = node.i + 1;
            nextRight.j = node.j;
            nextRight.endNode = end(nextRight.i, nextRight.j);
            node.nextRight = nextRight;
            if (nextRight.endNode) {
                total++;
            } else {
                hasNext(nextRight);
            }
        }

        if (node.j < m) {
            Node1 nextDown =  new Node1();
            nextDown.num = node.num + 1;
            nextDown.i = node.i;
            nextDown.j = node.j + 1;
            nextDown.endNode = end(nextDown.i, nextDown.j);
            node.nextDown = nextDown;
            if (nextDown.endNode) {
                total++;
            } else {
                hasNext(nextDown);
            }
        }
    }

    static class Node1 {

        public int num;
        public boolean endNode;
        public int i;
        public int j;

        public Node1 nextRight = null;

        public Node1 nextDown = null;
    }


}

构建树，遍历所有符合条件的下一步，知道找到最后的节点，并计数。