洛谷题单算法1-7 搜索

2023-11-06

[USACO08FEB]Meteor Shower S

题目描述
Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.

The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) at time Ti (0 ≤ Ti ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.

Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).

Determine the minimum time it takes Bessie to get to a safe place.

牛去看流星雨，不料流星掉下来会砸毁上下左右中五个点。每个流星掉下的位置和时间都不同，求牛能否活命，如果能活命，最短的逃跑时间是多少？

输入格式

Line 1: A single integer: M
Lines 2…M+1: Line i+1 contains three space-separated integers: Xi, Yi, and Ti

输出格式

Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

题意翻译
贝茜听说了一个骇人听闻的消息：一场流星雨即将袭击整个农场，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽，届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，贝茜开始担心自己的安全问题。以 Farmer John 牧场中最聪明的奶牛的名誉起誓，她一定要在被流星砸到前，到达一个安全的地方（也就是说，一块不会被任何流星砸到的土地）。如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。根据预报，一共有 M 颗流星(1≤M≤50,000) 会坠落在农场上，其中第i颗流星会在时刻 Ti(0≤Ti ≤1,000) 砸在坐标为 (Xi,Yi ) (0≤Xi ≤300，0≤Yi≤300) 的格子里。流星的力量会将它所在的格子，以及周围 4 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。

贝茜在时刻 0 开始行动，它只能在第一象限中，平行于坐标轴行动，每 1 个时刻中，她能移动到相邻的（一般是 4 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦，那么贝茜只能在 t 之前的时刻在这个格子里出现。

请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。

Translated by @奆奆的蒟蒻 @跪下叫哥

输入输出样例
输入 #1复制
4
0 0 2
2 1 2
1 1 2
0 3 5
输出 #1复制
5

思路：很典型的bfs,但是需要注意的细节比较多。。。
我们用一个二维数组储存每个点陨石降落的时间，如果该点不会被陨石砸到，则标记为-1，如果可以被砸到，我们储存被砸到的最短时间。注意，一个点可能被砸到好几次！我们对于一个点只储存最早被砸到的时间。一个点被砸到还会烧焦周围的四个点，注意更新周围点的值（及时被砸到的点的值未被更新，也要去更新一下周围四个点）。
我们再用一个二维数组储存到达每个点的最短时间。我们采用队列的方式，每次入队列最后标记他。


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

public class Main{
    static int m,xi,yi,ti;
    static boolean[][] flag; //标记该点是否走过
    static LinkedList<Node> linkedList = new LinkedList<>();
    static int[][] ans,book,next={{-1,0},{0,1},{1,0},{0,-1}}; //到达该点的时间 标记陨石砸落在该点的时间 以及方向
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        ans = new int[305][305];
        book = new int[305][305];
        flag = new boolean[305][305];
        for(int i=0;i<book.length;i++){
            for(int j=0;j<book[i].length;j++){
                book[i][j] = -1;
            }
        }
        for(int i=0;i<m;i++){
            xi = sc.nextInt();
            yi = sc.nextInt();
            ti = sc.nextInt();
            if(book[xi][yi]==-1||book[xi][yi]>=ti){ //该点没被砸过 或者 这个时间更早
                book[xi][yi] = ti;
            }
            for(int j=0;j<4;j++){
                int tx = xi + next[j][0];
                int ty = yi + next[j][1];
                if(tx>=0&&ty>=0&&(book[tx][ty]==-1||book[tx][ty]>ti)){
                    book[tx][ty] = ti;
                }
            }
        }
        ans[0][0] = 0;
        flag[0][0]  = true;
        linkedList.add(new Node(0,0));
        while(linkedList.size()>0){
            int x0 = linkedList.getFirst().x;
            int y0 = linkedList.getFirst().y;
            int s0 = ans[x0][y0];
            if(book[x0][y0]==-1){
                System.out.print(s0);
                System.exit(0);
            }
            for(int i=0;i<4;i++){
                int tx = x0 + next[i][0];
                int ty = y0 + next[i][1];
                int ts = s0 + 1;
                if(tx>=0&&ty>=0&&!flag[tx][ty]&&(ts<book[tx][ty]||book[tx][ty]==-1)){
                    ans[tx][ty] = ts;
                    flag[tx][ty] = true;
                    linkedList.add(new Node(tx,ty));
                }
            }
            linkedList.remove(0);
        }
        System.out.print("-1");
    }
}
class Node{
    int x,y;

    public Node() {
    }

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

kkksc03考前临时抱佛脚

题目背景
kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述
这次期末考试，kkksc03 需要考 4 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1 ,s2,s3,s4道题目，完成每道题目需要一些时间，可能不等A1 ,A2 ,…,As1 ,B1,B2
,…,Bs2，C1,C2 ,…,Cs3 ，D1 ,D2,…,Ds4 ）。
kkksc03 有一个能力，他的左右两个大脑可以同时计算 2道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式
本题包含 5 行数据：第 1 行，为四个正整数 s1 ,s2 ,s3 ,s4 。
第 2行，为A1,A2 ,…,As1 共 s1个数，表示第一科习题集每道题目所消耗的时间。
第 3 行，为B1 ,B2 ,…,Bs2 共 s2个数。
第 4 行，为C1,C2,…,Cs3 共 s3个数。
第 5 行，为 D1 ,D2,…,Ds4 共 s 4个数，意思均同上。

输出格式
输出一行,为复习完毕最短时间。

输入输出样例
输入 #1复制
1 2 1 3
5
4 3
6
2 4 3
输出 #1复制
20
思路：dp，这题可以用01背包来做。将四科分开来看，对于每科存在一个背包，背包的容量是该科所有习题时间的一半。将背包看做价值和重量相等的背包。我们寻找不超过该科所有习题一半时间的最大时间的做法，用该组的总时间减去dp[t/2]便是该科目用的时间。



import java.util.Scanner;

public class Main{
    static int s1,s2,s3,s4,t1,t2,t3,t4;
    static int[] dp1,dp2,dp3,dp4,a,b,c,d;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s1 = sc.nextInt();
        s2 = sc.nextInt();
        s3 = sc.nextInt();
        s4 = sc.nextInt();
        dp1 = new int[2500];
        dp2 = new int[2500];
        dp3 = new int[2500];
        dp4 = new int[2500];
        a = new int[25];
        b = new int[25];
        c = new int[25];
        d = new int[25];
        for(int i=0;i<s1;i++){
            a[i] = sc.nextInt();
            t1+=a[i];
        }
        for(int i=0;i<s2;i++){
            b[i] = sc.nextInt();
            t2+=b[i];
        }
        for(int i=0;i<s3;i++){
            c[i] = sc.nextInt();
            t3+=c[i];
        }
        for(int i=0;i<s4;i++){
            d[i] = sc.nextInt();
            t4+=d[i];
        }
        for(int i=0;i<s1;i++){
            for(int j=t1/2;j>=a[i];j--){
                dp1[j] = Math.max(dp1[j],dp1[j-a[i]]+a[i]);
            }
        }
        for(int i=0;i<s2;i++){
            for(int j=t2/2;j>=b[i];j--){
                dp2[j] = Math.max(dp2[j],dp2[j-b[i]]+b[i]);
            }
        }
        for(int i=0;i<s3;i++){
            for(int j=t3/2;j>=c[i];j--){
                dp3[j] = Math.max(dp3[j],dp3[j-c[i]]+c[i]);
            }
        }
        for(int i=0;i<s4;i++){
            for(int j=t4/2;j>=d[i];j--){
                dp4[j] = Math.max(dp4[j],dp4[j-d[i]]+d[i]);
            }
        }
        System.out.print(t1+t2+t3+t4-dp1[t1/2]-dp2[t2/2]-dp3[t3/2]-dp4[t4/2]);
    }
}

[USACO10OCT]Lake Counting S

题目描述
Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (’.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水(‘W’) 或是旱地(’.’)。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入格式
Line 1: Two space-separated integers: N and M * Lines 2…N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

第1行：两个空格隔开的整数：N 和 M 第2行到第N+1行：每行M个字符，每个字符是’W’或’.’，它们表示网格图中的一排。字符之间没有空格。

输出格式
Line 1: The number of ponds in Farmer John’s field.

一行：水坑的数量

输入输出样例
输入 #1复制
10 12
W…WW.
.WWW…WWW
…WW…WW.
…WW.
…W…
…W…W…
.W.W…WW.
W.W.W…W.
.W.W…W.
…W…W.
输出 #1复制
3

思路：bfs和dfs都可以。蓝桥杯貌似考过差不多的。。。

bfs:



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

public class Main{
    static char[][] ch;
    static int n,m,count=1;
    static int[][] book = new int[110][110],next = {{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{-1,1},{1,1},{1,-1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        ch = new char[110][110];
        for(int i=0;i<n;i++){
            ch[i] = sc.next().toCharArray();
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(ch[i][j]=='W'&&book[i][j]==0){
                    book[i][j]=count;
                    LinkedList<Node> linkedList = new LinkedList<>();
                    linkedList.add(new Node(i,j));
                    while(linkedList.size()>0){
                        int x0 = linkedList.getFirst().x;
                        int y0 = linkedList.getFirst().y;
                        for(int k=0;k<8;k++){
                            int tx = x0+next[k][0];
                            int ty = y0+next[k][1];
                            if(tx>=0&&tx<n&&ty>=0&&ty<m&&ch[tx][ty]=='W'&&book[tx][ty]==0){
                                book[tx][ty] = count;
                                linkedList.add(new Node(tx,ty));
                            }
                        }
                        linkedList.remove(0);
                    }
                    count++;
                }
            }
        }
        System.out.print(count-1);
    }
}
class Node{
    int x,y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

dfs:



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

public class Main{
    static char[][] ch;
    static int n,m,count=1;
    static int[][] book = new int[110][110],next = {{-1,0},{0,1},{1,0},{0,-1},{-1,-1},{-1,1},{1,1},{1,-1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        ch = new char[110][110];
        for(int i=0;i<n;i++){
            ch[i] = sc.next().toCharArray();
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(ch[i][j]=='W'&&book[i][j]==0){
                    book[i][j]=count;
                    dfs(i,j);
                    count++;
                }
            }
        }
        System.out.print(count-1);
    }
    public static void dfs(int x,int y){
        for(int k=0;k<8;k++){
            int tx = x+next[k][0];
            int ty = y+next[k][1];
            if(tx>=0&&tx<n&&ty>=0&&ty<m&&ch[tx][ty]=='W'&&book[tx][ty]==0){
                book[tx][ty] = count;
                dfs(tx,ty);
            }
        }
    }
}

[USACO1.5]八皇后 Checker Challenge

题目描述
一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

在这里插入图片描述

上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i 个数字表示在第 i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

输入格式
一行一个正整数 n，表示棋盘是 n×n 大小的。

输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例
输入 #1复制
6
输出 #1复制
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
说明/提示
【数据范围】
对于 100% 的数据，6≤n≤13。

思路：经典的八皇后问题，递归+回溯。需要注意的是我们要采用标记每列，每个对角线的情况，不然的话会超时。我们用c[x+i]和d[x-i+n]记录每条对角线。



import java.util.Scanner;

public class Main{
     static int n,count;
     static int[] a,b,c,d;
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        n = sc.nextInt();
        a = new int[105];
        b = new int[105];
        c = new int[105];
        d = new int[105];
        fun(1);
        System.out.print(count);
    }
    public static void fun(int x){ //放置第x行
        if(x==n+1){
            count++;
            if(count<=3) {
                for (int i = 1; i <= n; i++) {
                    System.out.print(a[i] + " ");
                }
                System.out.println();
            }
            return ;
        }
        for(int i=1;i<=n;i++){
            if(b[i]==0&&c[i+x]==0&&d[x-i+n]==0){
                a[x] = i;
                b[i] = 1;
                c[i+x] = 1;
                d[x-i+n] = 1;
                fun(x+1);
                b[i]=0;
                c[i+x] = 0;
                d[x-i+n] = 0;
            }
        }
    }
}

奇怪的电梯

题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1≤i≤N)上有一个数字ki(0≤Ki ≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3, 3 ,1 ,2 ,5代表了Ki (K1 =3,K2 =3,…)，从1楼开始。在1楼，按“上”可以到4楼，按“下”是不起作用的，因为没有−2楼。那么，从A楼到B楼至少要按几次按钮呢？

输入格式
共二行。

第一行为3个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)。

第二行为N个用空格隔开的非负整数，表示Ki 。

输出格式
一行，即最少按键次数,若无法到达，则输出−1。

输入输出样例
输入 #1复制
5 1 5
3 3 1 2 5
输出 #1复制
3
思路：bfs…



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

public class Main{
    static int n,m,a,b,x0,y0;
    static int[] k = new int[205],count = new int[205];
    static LinkedList<Node> linkedList = new LinkedList<>();
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        n = sc.nextInt();
        a = sc.nextInt();
        b = sc.nextInt();
        for(int i=1;i<=n;i++){
            k[i] = sc.nextInt();
            count[i] = -1;
        }
        count[a] = 0;
        linkedList.add(new Node(a,k[a],0));
        while(linkedList.size()>0){
            int sum = linkedList.getFirst().sum+1;
            int t1 = linkedList.getFirst().x+linkedList.getFirst().k;
            int t2 = linkedList.getFirst().x-linkedList.getFirst().k;
            if(t1>=1&&t1<=n&&count[t1]==-1){
                count[t1] = sum;
                linkedList.add(new Node(t1,k[t1],sum));
            }
            if(t2>=1&&t2<=n&&count[t2]==-1){
                count[t2] = sum;
                linkedList.add(new Node(t2,k[t2],sum));
            }
            linkedList.remove(0);
        }
        System.out.print(count[b]);
    }
}
class Node{
    int x,k,sum;

    public Node() {
    }

    public Node(int x, int k,int sum) {
        this.x = x;
        this.k = k;
        this.sum = sum;
    }
}

马的遍历

题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入格式
一行四个数据，棋盘的大小和马的坐标

输出格式
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

输入输出样例
输入 #1复制
3 3 1 1
输出 #1复制
0 3 2
3 -1 1
2 1 4

思路：bfs。先将数组初始化为-1，根据步数更新值。注意输出时候空格的数量。



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

public class Main{
    static int n,m,x0,y0;
    static int[][] book = new int[405][405],next = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,-2},{2,-1},{2,1},{1,2}};
    static LinkedList<Node> linkedList = new LinkedList<>();
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        x0 = sc.nextInt();
        y0 = sc.nextInt();
        for(int i=0;i<book.length;i++){
            for(int j=0;j<book[i].length;j++){
                book[i][j] = -1;
            }
        }
        book[x0][y0]=0;
        linkedList.add(new Node(x0,y0,0));
        while(linkedList.size()>0){
            int tx = linkedList.getFirst().x;
            int ty = linkedList.getFirst().y;
            int ts = linkedList.getFirst().sum;
            for(int i=0;i<8;i++){
                int x1 = tx+next[i][0];
                int y1 = ty+next[i][1];
                if(x1>=1&&x1<=n&&y1>=1&&y1<=m&&book[x1][y1]==-1){
                    book[x1][y1] = ts+1;
                    linkedList.add(new Node(x1,y1,ts+1));
                }
            }
            linkedList.remove(linkedList.getFirst());
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(book[i][j]>=0&&book[i][j]<10)
                    System.out.print(book[i][j]+"    ");
                else if(book[i][j]==-1||book[i][j]>=10&&book[i][j]<100)
                    System.out.print(book[i][j]+"   ");
                else
                    System.out.print(book[i][j]+"  ");
            }
            System.out.println();
        }
    }
}
class Node{
    int x,y,sum;

    public Node() {
    }

    public Node(int x, int y, int sum) {
        this.x = x;
        this.y = y;
        this.sum = sum;
    }
}

选数

题目描述
已知 n 个整数x1,x2 ,…,xn，以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3,4个整数分别为3,7,12,19时，可得全部的组合与它们的和为：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

输入格式
键盘输入，格式为：
n,k(1≤n≤20,k<n)
x1,x2 ,…,xn(1≤xi≤5000000)

输出格式
屏幕输出，格式为： 1个整数（满足条件的种数）。

输入输出样例
输入 #1复制
4 3
3 7 12 19
输出 #1复制
1
思路：搜索，数据范围很小，爆搜就完了。函数参数代表判断了x个数，选了y个数。最后判断一下所选的k个数的和是不是素数即可。



import java.util.Scanner;

public class Main{
    static int n,k,count;
    static int[] arr,book;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        arr = new int[25];
        book = new int[25];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        dfs(0,0);
        System.out.print(count);
    }
    public static void dfs(int x,int y){ //判断了x个数 选了y个
            if(x==n){
                if(y==k){
                    int sum = 0;
                    for(int i=0;i<k;i++){
                        sum+=book[i];
                    }
                    if(ok(sum)){
                        count++;
                    }
                }
                return ;
            }
            dfs(x+1,y);
            book[y]=arr[x];
            dfs(x+1,y+1);
    }
    public static boolean ok(int x){//判断x是否是素数
        if(x<2){
            return false;
        }
        for(int i=2;i*i<=x;i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }
}

[COCI2008-2009#2] PERKET

题目描述
Perket 是一种流行的美食。为了做好 Perket，厨师们必须小心选择配料，以便达到更好的口感。你有N种可支配的配料。对于每一种配料，我们知道它们各自的酸度 S 和甜度 B。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的甜度为每一种配料的甜度的总和。

众所周知，美食应该口感适中；所以我们希望选取配料，以使得酸度和甜度的绝对差最小。

另外，我们必须添加至少一种配料，因为没有美食是以白水为主要配料的。

输入格式
第一行包括整数 N，表示可支配的配料数。

接下来 N 行，每一行为用空格隔开的两个整数，表示每一种配料的酸度和甜度。

输入数据保证，如果我们添加所有配料，总的酸度和甜度都不会超过 10^9 。

输出格式
输出酸度和甜度的最小的绝对差。

输入输出样例
输入 #1复制
1
3 10

输出 #1复制
7
输入 #2复制
4
1 7
2 6
3 8
4 9
输出 #2复制
1

思路：爆搜，维护一个最小值即可。



import java.util.Scanner;

public class Main{
    static int n;
    static long min = 999999999;
    static int[] book = new int[15];
    static int[][] arr = new int[15][2];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i=0;i<n;i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        dfs(0);
        System.out.print(min);
    }
    public static void dfs(int x){
        if(x==n){
            long t1 = 1;
            long t2 = 0;
            boolean flag = false;
            for(int i=0;i<n;i++){
                if(book[i]==1){
                    flag = true;
                    t1*=arr[i][0];
                    t2+=arr[i][1];
                }
            }
            if(flag){
                min = Math.min(Math.abs(t2-t1),min);
            }
            return ;
        }
        dfs(x+1);
        book[x]=1;
        dfs(x+1);
        book[x]=0;
    }
}

迷宫

题目背景
给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

题目描述
无

输入格式
第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。

输出格式
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。

输入输出样例
输入 #1复制
2 2 1
1 1 2 2
1 2
输出 #1复制
1
思路：最基础的dfs.



import java.util.Scanner;

public class Main{
    static int n,m,t,x0,y0,x1,y1,count;
    static int[][] book,next = {{-1,0},{0,1},{1,0},{0,-1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        t = sc.nextInt();
        x0 = sc.nextInt();
        y0 = sc.nextInt();
        x1 = sc.nextInt();
        y1 = sc.nextInt();
        book = new int[10][10];
        for(int i=0;i<t;i++){
            int tx = sc.nextInt();
            int ty = sc.nextInt();
            book[tx][ty] = -1;
        }
        book[x0][y0]=1;
        dfs(x0,y0);
        System.out.print(count);
    }
    public static void dfs(int x,int y) {
        if(x==x1&&y==y1){
            count++;
            return ;
        }
        for(int i=0;i<4;i++){
            int tx = x +next[i][0];
            int ty = y +next[i][1];
            if(tx>=1&&tx<=n&&ty>=1&ty<=m&&book[tx][ty]==0){
                book[tx][ty]=1;
                dfs(tx,ty);
                book[tx][ty]=0;
            }
        }
    }
}

自然数拆分

题目描述
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式
输入：待拆分的自然数n。

输出格式
输出：若干数的加法式子。

输入输出样例
输入 #1复制
7
输出 #1复制
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

思路：dfs,注意为了避免重复，我们将选择数据时要不小于前面选的数。

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main{
    static int n;
    static int[] arr = new int[100];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(1,0,0);
    }
    public static void dfs(int frist,int sum,int count){ //和是sum 选了count个数
        if(sum==n){
            for(int i=0;i<count;i++){
                if(i==count-1){
                    System.out.println(arr[i]);
                }else{
                    System.out.print(arr[i]+"+");
                }
            }
            return ;
        }
        if(sum>n){
            return ;
        }
        for(int i=frist;i<n;i++){
            arr[count] = i;
            dfs(i,sum+i,count+1);
        }
    }
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)