迷宫
题目要求：
Extense 处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense 想要从点A走到点 B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
输入要求：
输入迷宫的行（行和列是相等的），然后输入迷宫的状态，然后再输入起始位置和终止位置的行和列
输出要求：
如果可以走到，就输出成功
输入样例
2
..
..
0 0 1 1
输出样例
成功！
import java.util.Scanner;
//迷宫
public class LX9_3 {
private static int n;//迷宫的行和列数，行列相等
private static char[][] a;//保存迷宫的状态
private static int endx;
private static int endy;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
a=new char[n][n];
String l=sc.nextLine();
//得到迷宫的状态
for(int i=0;i<n;i++)
{
String s=sc.nextLine();
for(int j=0;j<n;j++)
{
//System.out.println(s.charAt(j));
a[i][j]=s.charAt(j);
}
}
int startx=sc.nextInt();//初始位置的行
int starty=sc.nextInt();//初始位置的列
endx=sc.nextInt();//结束位置的行
endy=sc.nextInt();//结束位置的列
f(startx-1,starty-1);
}
//判断从i,j 位置是否到达想要到达的位置
public static void f(int i,int j)
{
if(i<0||j<0||i>=n||j>=n)//走出迷宫
{
return;
}
if(a[i][j]=='#')//不能通过
return;
if(i==endx-1&&j==endy-1)//成功
{
System.out.println("成功！");
}
else//继续递归
{
a[i][j]='#';//将走过的格子置为走过，否则会出现死循环
f(i-1,j);
f(i+1,j);
f(i,j-1);
f(i,j+1);
a[i][j]='.';
}
}
}
注意：回溯 枚举
算24
题目要求：
给出 4 个小于 10 个正整数，你可以使用加减乘除 4 种运算以及括号把这 4 个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于 24。
这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。 比如，对于 5，5，5，1，我们知道 5 * (5 – 1 / 5) = 24，因此可以得到 24。又比如，对于 1，1，4，2，我们怎么都不能得到 24。
输入要求
输入四个小于10的整数
输出
如果有则输出成功，如果没有不输出
输入样例
1 5 5 5输出样例
成功！
import java.util.Scanner;
//算24
public class LX9_4 {
private static int[] a=new int[4];//保存输入的4个整数
private static boolean[] flag=new boolean[4];//标记数是否用过
private static float sum=0;//保存结果
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
//得到4个小于10的整数
for(int i=0;i<4;i++)
{
a[i]=sc.nextInt();
}
for(int i=0;i<4;i++)
{
sum=0;
if(flag[i]) continue;//该数用过 直接跳过
else
{
flag[i]=true;
sum=a[i];
if(f(1))
break;
else
sum-=a[i];
sum-=a[i];//此处实现-1/5的情况（5-1/5）*5=24
if(f(1))
break;
else
sum+=a[i];
sum=a[i];
if(f(1))
break;
else
sum=a[i];
sum=a[i];
if(f(1))
break;
else
sum=a[i];
}
flag[i]=false;
}
}
//从第i个数到最后的结果是否为24
public static boolean f(int i)
{
if(i==4)
{
if(sum==24)
{
System.out.println("成功！");
return true;
}
else
{
return false;
}
}
else
{
for(int j=0;j<4;j++)
{
if(flag[j]) continue;//该数用过 直接跳过
else
{
flag[j]=true;
sum+=a[j];
if(f(i+1))
return true;
else
sum-=a[j];//回溯
sum-=a[j];
if(f(i+1))
return true;
else
sum+=a[j];//回溯
sum*=a[j];
if(f(i+1))
return true;
else
sum/=a[j];//回溯
sum/=a[j];
if(f(i+1))
return true;
else
sum*=a[j];//回溯
}
flag[j]=false;//回溯
}
return false;
}
}
}
注意：枚举 回溯
小游戏（和迷宫很像）
题目要求：
一天早上，你起床的时候想：“我编程序这么牛，为什么不能靠这个赚点小钱呢？”因此你决定编写一个小游戏。 游戏在一个分割成 w * h个正方格子的矩形板上进行。如图所示，每个正方格子上可以有一张游戏卡片，当然也可以没有。 当下面的情况满足时，我们认为两个游戏卡片之间有一条路径相连： 路径只包含水平或者竖直的直线段。路径不能穿过别的游戏卡片。但是允许路径临时的离开矩形板。下面是一个例子：
注意：图中牌的位置行和列反着
这里在 (1, 3)和 (4, 4)处的游戏卡片是可以相连的。而在 (2, 3) 和 (3, 4) 处的游戏卡是不相连的，因为连接他们的每条路径都必须要穿过别的游戏卡片。 你现在要在小游戏里面判断是否存在一条满足题意的路径能连接给定的两个游戏卡片。
输入要求;
输入矩形板的的行），然后输入矩形板的状态（1代表有牌，0代表没牌），然后再输入起始位置和终止位置的行和列
输出要求：
如果可以走到，就输出成功
输入样例
4 5
10001
11101
01110
3 2 3 5
输出样例
成功！注意：此处和迷宫不同的是，矩形板外的区域也可以走，思路是扩展矩形板将行和列都增加2，并且将其置为可通过。这样问题就可以和迷宫一样解决了
import java.util.Scanner;
//小游戏（迷宫的变形）
public class LX9_6 {
private static int w;//行
private static int h;//列
private static int[][] a;//保存矩形板的情况 0代表可以通行，1代表不可以通行
private static int endx;//结束位置的行
private static int endy;//结束位置的列
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
w=sc.nextInt();
h=sc.nextInt();
/*因为在矩形框的外边也可以通过，所以将矩形板的行和列都增加2*/
a=new int[w+2][h+2];
// 得到矩形板的情况
String l=sc.nextLine();
for(int i=1;i<w+1;i++)
{
String s=sc.nextLine();
for(int j=1;j<h+1;j++)
{
a[i][j]=s.charAt(j-1)-'0';
}
}
int startx=sc.nextInt();//初始位置的行
int starty=sc.nextInt();//初始位置的列
a[startx][starty]=0;//将起始位置置为可以通过
endx=sc.nextInt();//结束位置的行
endy=sc.nextInt();//结束位置的列
a[endx][endy]=0;//将结束位置置为可以通过
for(int i=1;i<w+1;i++)
{
for(int j=1;j<h+1;j++)
{
System.out.print(a[i][j]+" ");
}
System.out.println();
}
f(startx,starty);
}
//判断从i,j 位置是否到达想要到达的位置
public static void f(int i,int j)
{
if(i<0||j<0||i>=w+2||j>=h+2)//走出扩展后的矩形板
{
return;
}
if(a[i][j]==1)//不能通过
{
//System.out.println(i+" "+j+" "+a[i][j]);
return;
}
else
{
if(i==endx&&j==endy)
{
System.out.println("成功！");
}
else
{
//System.out.println(i+" "+j);
a[i][j]=1;//将走过的格子置为走过(也就是置为不能通过)，否则会出现死循环
f(i-1,j);
f(i+1,j);
f(i,j-1);
f(i,j+1);
a[i][j]=0;//回溯
}
}
}
}
注意：枚举 回溯
碎纸机
题目要求：
你现在负责设计一种新式的碎纸机。一般的碎纸机会把纸切成小片，变得难以阅读。而你设计的新式的碎纸机有以下的特点：
1.每次切割之前，先要给定碎纸机一个目标数，而且在每张被送入碎纸机的纸片上也需要包含一个数。
2.碎纸机切出的每个纸片上都包括一个数。
3.要求切出的每个纸片上的数的和要不大于目标数而且与目标数最接近。
举一个例子，如下图，假设目标数是50，输入纸片上的数是12346。碎纸机会把纸片切成 4块，分别包含 1，2，34和 6。这样这些数的和是 43 (= 1 + 2 + 34 + 6)，这是所有的分割方式中，不超过 50，而又最接近 50的分割方式。又比如，分割成1，23，4和 6是不正确的，因为这样的总和是 34 (= 1 + 23 + 4 + 6)，比刚才得到的结果 43 小。分割成 12，34 和 6 也是不正确的，因为这时的总和是52 (= 12 + 34 + 6)，超过了50。
还有三个特别的规则：
1.如果目标数和输入纸片上的数相同，那么纸片不进行切割。
2.如果不论怎样切割，分割得到的纸片上数的和都大于目标数，那么打印机显示错误信息。
3.如果有多种不同的切割方式可以得到相同的最优结果。那么打印机显示拒绝服务信息。比如，如果目标数是 15，输入纸片上的数是 111，那么有两种不同的方式可以得到最优解，分别是切割成 1 和11 或者切割成 11 和1，在这种情况下，打印机会显示拒绝服务信息。 为了设计这样的一个碎纸机，你需要先写一个简单的程序模拟这个打印机的工作。给定两个数，第一个是目标数，第二个是输入纸片上的数，你需要给出碎纸机对纸片的分割方式。
输入要求
输入目标数和纸片上的数（都不超过整型所能表示的范围）
输出要求
输出最接近目标数且不大于目标数的值
输入样例
50
12346
输出样例
43
import java.math.BigInteger;
import java.util.Scanner;
//碎纸机
public class LX9_7 {
private static int[] a;//保存纸片上的数字的每一位
private static int len;//纸片上的数字的位数
private static int target;//目标数
private static int[] temp;//放置隔板的位置，元素存的是隔板前的元素的下标
private static int[] temp2;//保存输出结果的每个隔板的位置
private static int large=0;//保存最后输出的那个值
private static int flag=0;//标记最接近数的个数
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
target=sc.nextInt();//得到目标数字
sc.nextLine();
String s=sc.nextLine();//得到纸片上的数据
//System.out.println(s);
len=s.length();//纸片上数据的长度
a=new int[len];
temp=new int[len];
temp2=new int[len];
//获得数字的每一位
int sum3=0;
for(int i=0;i<len;i++)
{
//System.out.println(s.charAt(i)-'0');
a[i]=s.charAt(i)-'0';
sum3=sum3*10+a[i];
}
if(sum3==target)
{
System.out.println("目标数和纸片上数据相等！");
return;
}
for(int i=1;i<=len-1;i++)
{
f(i,0,0);
}
if(flag>=1)
{
System.out.println("最接近目标数有多重分割方法!");
return;
}
if(large==0)
{
System.out.println("所有的分割都大于目标数！");
}
else
{
System.out.println(large);
//输出结果值的每个隔板的位置
for(int i=0;i<len;i++)
{
System.out.print(temp2[i]+" ");
}
System.out.println();
}
}
//num隔板的个数，index代表隔板可以放在从该下标表示的元素后面， cur当前放的是第几个隔板
public static void f(int num,int index,int cur)
{
if(cur==num)//num个隔板都放置完毕
{
temp[num]=len-1;
int sum=0;
int t=0;
for(int i=0;i<=num;i++)
{
int sum2=0;
for(int j=t;j<=temp[i];j++)
{
sum2=sum2*10+a[j];
}
sum+=sum2;
t=temp[i]+1;
}
//System.out.println(sum);
if(sum>target)//和大于目标值，返回
return;
else
{
if(sum>large)//和接近目标值
{
flag=0;
large=sum;
for(int i=0;i<=num;i++)
{
temp2[i]=temp[i];
}
}
else if(sum==large)
{
flag++;
}
return;
}
}
if(index>=len-1)//隔板数没有放完，但是能放置的位置已经没有了
{
//System.out.println("0000");
return;
}
else
{
for(int i=index;i<=len-2;i++)
{
//System.out.println(i);
temp[cur]=i;
f(num,i+1,cur+1);
}
}
}
}
注意：思路（放隔板的个数） 递归函数