Angwauh


私信TA

用户名:1710113018

访问量:28476

签 名:

你脚下曾踏过的泥沼,是你涤荡着强大的最好印证!

等  级
排  名 72
经  验 7889
参赛次数 6
文章发表 42
年  龄 19
在职情况 在职
学  校 河南农业大学
专  业 软件技术

  自我简介:

解题思路:求所有路径问题多用dfs,首先建立一个二维数组来保存情况,a[][]==0为可走点,a[][]==1为不可走点。

注意事项:

参考代码:

import java.util.Scanner;

public class Main {
    static long s =0;    //保存可行情况
    static int a[][];
    private static void dfs(int x, int y, int[][] a) {
        if(x<0||x>a.length-1||y<0||y>a[0].length-1)        //判断该点是否超界
            return;
        if(a[x][y]==1)                                     //判断该点是否为马的控制点
            return;
        if(x==a.length-1&&y==a[0].length-1) {              //是否到达B点
            s++;
            return;
        }
        dfs(x+1, y, a);                                    //向下走
        dfs(x, y+1, a);                                    //向右走
        
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //马的控制点的8个方向
        int b[][] = { { -2, -1 }, { -1, -2 }, { 1, -2 }, { 2, -1 }, { 2, 1 }, { 1, 2 }, { -1, 2 }, { -2, 1 } };
        int n = scanner.nextInt()+1;
        int m = scanner.nextInt()+1;
        int x = scanner.nextInt();
        int y = scanner.nextInt();
         a = new int[n][m];
         a[x][y] = 1;
         //找出马的控制点,置a[x][y] = 1
        for (int i = 0; i < 8; i++) {
            int d1 = b[i][0] + x;
            int d2 = b[i][1] + y;
            if (d1 < 0 || d1 >= m || d2 < 0 || y >= n)
                continue;
            a[d1][d2] = 1;
        }
        dfs(0, 0, a);
        System.out.println(s);
    }
}


 

0.0分

1 人评分

  评论区