DFS算法练习 POJ1111; POJ1129; POJ2245; POJ2657

POJ1111:

import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/9/27 9:49
 * @Description
 * @Since version-1.0
 */
public class Main {
    /**
     * 行
     */
    static int r;
    /**
     * 列
     */
    static int c;
    /**
     * 初始坐标
     */
    static int x;
    static int y;
    /**
     * 图像数组
     */
    static char[][] img;
    /**
     * 标记数组
     */
    static int[][] mark;
    /**
     * 周长
     */
    static int perimeter;



    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            String str = sc.nextLine();
            String[] s = str.split(" ");
            r = Integer.parseInt(s[0]);
            c = Integer.parseInt(s[1]);
            x = Integer.parseInt(s[2])-1;
            y = Integer.parseInt(s[3])-1;
            if (r==0 && c==0 && x==-1 && y==-1) {
                break;
            }
            img = new char[r][c];
            mark = new int[r][c];
            for (int i = 0; i < r; i++) {
                String s1 = sc.nextLine();
                char[] c1 = s1.toCharArray();
                for (int j = 0; j < c; j++) {
                    img[i][j] = c1[j];
                }
            }
            perimeter = 0;
            dfs(x,y);
            System.out.println(perimeter);
        }
    }
    /**
     * 方向数组
     */
    private static int[] dirX = {0,1,0,-1,-1,1,-1,1};
    private static int[] dirY = {1,0,-1,0,-1,1,1,-1};
    private static void dfs(int x, int y) {
        /*dfs所有'X'*/
        if (img[x][y]=='X'&&mark[x][y]==0){
            mark[x][y]=1;
            for (int i = 0; i < 8; i++) {
                int a = x+dirX[i];
                int b = y+dirY[i];
                boolean bl1 = a>=0&&b>=0&&a<r&&b<c;

                /*如果出界或者是'.'*/
                if (!bl1 || img[a][b] == '.'){
                    /*累计边长*/
                    if (i<4){
                        perimeter++;
                    }
                }else {
                    dfs(a,b);
                }
            }
        }
    }
}

POJ1129:

import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/9/24 17:49
 * @Description
 * @Since version-1.0
 */
public class Main {
    /**
     * 中继器数量
     */
    static int n;
    /**
     * 中继器地图数组
     */
    static int[][] map;
    /**
     * 频道分配数组
     */
    static int[] distribute;
    /**
     * 用来记录频道数为2,3,4时分别的分配方案数
     */
    static int[] scheme = new int[3];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            /*获取第一个数字，即中继器数量*/
            n=sc.nextInt();
            /*如果数量为0，则结束*/
            if (n==0){
                break;
            }
            /*初始化中继器地图数组和频道数组*/
            map = new int[n][n];
            distribute = new int[n];
            scheme = new int[3];
            boolean side = false;
            /*接收一组数据输入，给数组赋值*/
            for (int i = 0; i < n; i++) {
                String str = sc.next();
                /*每个中继器按字母表顺序用字母表示，可以用第i个字母-第一个
                字母A，利用ASCII码之差得到对应字母在字母表中的序数，*/
                int charNum = str.charAt(0) - 'A';
                /*获取第一个字母表示的中继器相邻的其他中继器*/
                for (int j = 2; j < str.length(); j++) {
                    /*获取字母对应的序数*/
                    int adja = str.charAt(j)-'A';
                    map[charNum][adja]=1;
                    map[adja][charNum]=1;
                    side=true;
                }
            }
            int channel = 1;
            if (side){
               dfs(0,0,distribute);
               /*排错点1：*/
                /*System.out.println(Arrays.toString(scheme));*/
                for (int i = 0; i < 3; i++) {
                    if (scheme[i]!=0){
                        channel=i+2;
                        System.out.println(channel+" channels needed.");
                        break;
                    }
                }
            }else {
                System.out.println("1 channel needed.");
            }


        }
    }


    /**
     * @param r 当前中继器编号
     * @param c 当前子树能使用的频道数
     * @param d 当前的频道安排情况
     * @return
     */
    private static void dfs(int r,int c,int[] d){
        if (r==0){
            for (int i = 2; i <= 4; i++) {
                d=new int[n];
                dfs(1,i,d);
            }
        }else {
            if (r==n+1){
                scheme[c-2]++;
                return;
            }
            /*遍历当前能使用的频道数*/
            for (int i = 1; i <= c; i++) {
                /*对第r个中继器安排i频道*/
                d[r-1]=i;
                if (satisfied(r,c,d)){
                    /*排错点2：*/
/*                    System.out.println(r+""+c+Arrays.toString(d)+Arrays.toString(scheme));*/
                    dfs(r+1,c,d);
                }
                /*回溯省略，下一层循环自动刷新*/
            }
        }


    }

    /**
     * @param r 当前中继器编号
     * @param c 当前子树能使用的频道数
     * @param d 当前的频道安排情况
     * @return
     */
    private static boolean satisfied(int r,int c,int[]d){
        /*剪枝条件，如果当前限制的频道数(或前一个限制)还未找到一个符合条件的方案*/
        boolean condition = (c==2&&scheme[c-2]==0)||(c>2&&scheme[c-2]==0&&scheme[c-3]==0);
        if (condition){
            /*遍历地图找到当前中继器邻接的其他中继器，依次对比是否符合条件*/
            for (int i = 0; i < n; i++) {
                if (map[r-1][i]==1&&d[r-1]==d[i]){
                    /*排错点3：*/
                    /*System.out.println("r-1="+(r-1)+";  i="+i+"; d[r-1]="+d[r-1]+";  d[i]="+d[i]+";  map[r-1][i]="+map[r-1][i]);*/
                    return false;
                }
            }
            return true;
        }
        return false;
    }

}

POJ2245:

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/9/27 12:52
 * @Description
 * @Since version-1.0
 */
public class Main {
    /**
     * 集合长度
     */
    static int k;
    /**
     * 集合
     */
    static int[] set;

    /**
     * 固定取6个数
     */
    static int m = 6;
    /**
     * 所有子集
     */
    static ArrayList<int[]> sub;

    /**
     * 当前子集
     */
    static int[] currSub;
    /**
     * 被选过的数
     */
    static boolean[] selected;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            /*数据输入和初始化*/
            String str = sc.nextLine();
            String[] s1 = str.split(" ");
            k = Integer.parseInt(s1[0]);
            if (k==0){
                break;
            }
            set = new int[k];
            currSub = new int[m];
            selected = new boolean[k];
            sub = new ArrayList<int[]>();
            for (int i = 0; i < k; i++) {
                set[i] = Integer.parseInt(s1[i+1]);
            }
            /*搜索*/
            dfs(0);
            /*打印*/
            for (int i = 0; i < sub.size(); i++) {
                int[] subSetI = sub.get(i);
                for (int j = 0; j < m; j++) {
                    if (j==m-1){
                        System.out.println(subSetI[j]);
                    }else {
                        System.out.print(subSetI[j]+" ");
                    }
                }
            }
            System.out.println("");
        }


    }

    /**
     * @param l 解空间树的层数，当前子集的第几个数
     */
    private static void dfs(int l) {
        if (l==m){
            /*到达叶子节点，放入子集集合中*/
            int[] sub1 = new int[m];
            System.arraycopy(currSub, 0, sub1, 0, m);
            sub.add(sub1);
            return;
        }
        for (int i = 0; i < k; i++) {
            /*当前set[i]没被选过并且大于当前子集的前一个数(字典序)*/
            boolean bl = !selected[i]&&(l==0||(l>0&&set[i]>currSub[l-1]));
            if (bl){
                /*填入当前子集，并锁定set中的当前数字*/
                currSub[l]=set[i];
                selected[i]=true;
                dfs(l+1);
                /*回溯*/
                selected[i]=false;
                currSub[l]=0;
            }
        }
    }
}

POJ2657:

import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/9/27 16:32
 * @Description
 * @Since version-1.0
 */
public class Main {
    /**
     * 圆环格数
     */
    static int n;
    /**
     * 目标编号
     */
    static int z;
    /**
     * 阻碍标记数组
     */
    static boolean[] m;

    /**
     * 找到目标
     */
    static boolean succeed;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            String str = sc.nextLine();
            String[] s = str.split(" ");
/*            if (s[0]==" "){
                break;
            }*/
            n = Integer.parseInt(s[0]);
            z = Integer.parseInt(s[1]);
            m = new boolean[n];
            int t = Integer.parseInt(s[2]);
            if (t!=0){
                String str2 = sc.nextLine();
                String[] s2 = str2.split(" ");
                /*标记阻碍格*/
                for (int i = 0; i < t; i++) {
                    m[Integer.parseInt(s2[i])-1]=true;
                }
            }
            succeed = false;
            for (int i = 1; i < n; i++) {
                dfs(0,i);
                if (succeed){
                    System.out.println(i);
                    break;
                }
            }

        }
    }

    /**
     * @param index 当前下标
     * @param k 当前子树的k
     */
    private static void dfs(int index, int k) {
        /*找到目标*/
        if (index==z-1){
            succeed = true;
            return;
        }
        /*遇到阻碍块或者重复块(说明会一直重复跳不到k)，直接结束当前分支*/
        if (m[index]){
            return;
        }
        /*标记当前块*/
        m[index]=true;
        /*跳跃下一步，如果出界就求余循环*/
        if (index+k<n){
            dfs(index+k,k);
        }else {
            dfs((index+k)%(n-1),k);
        }
        /*回溯*/
        m[index]=false;
    }
}