搜索回溯
本文最后更新于 480 天前,其中的信息可能已经有所发展或是发生改变。

 

 

 

X 星球的一处迷宫游乐场建在某个小山坡上。它是由
10
×
10
10×10 相互连通的小房间组成的。

房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立,则:


L 表示走到左边的房间,

R 表示走到右边的房间,

U 表示走到上坡方向的房间,

D 表示走到下坡方向的房间。
X 星球的居民有点懒,不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此!

开始的时候,直升机把
100
100 名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码…、
char[][] a={
{‘0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′,’0’},
{‘0′,’U’,’D’,’D’,’L’,’U’,’U’,’L’,’R’,’U’,’L’,’0′},
{‘0′,’U’,’U’,’R’,’L’,’L’,’L’,’R’,’R’,’R’,’U’,’0′},
{‘0′,’R’,’R’,’U’,’U’,’R’,’L’,’D’,’L’,’R’,’D’,’0′},
{‘0′,’R’,’U’,’D’,’D’,’D’,’D’,’U’,’U’,’U’,’U’,’0′},
{‘0′,’U’,’R’,’U’,’D’,’L’,’L’,’R’,’R’,’U’,’U’,’0′},
{‘0′,’D’,’U’,’R’,’L’,’R’,’L’,’D’,’L’,’R’,’L’,’0′},
{‘0′,’U’,’L’,’L’,’U’,’R’,’L’,’L’,’R’,’D’,’U’,’0′},
{‘0′,’R’,’D’,’L’,’U’,’L’,’L’,’R’,’D’,’D’,’D’,’0′},
{‘0′,’U’,’U’,’D’,’D’,’U’,’D’,’U’,’D’,’L’,’L’,’0′},
{‘0′,’U’,’L’,’R’,’D’,’L’,’U’,’U’,’R’,’R’,’R’,’0′},
{‘0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′,’0′}};

int sum=0;
int row;
int low;
int n=0;
for(int i=1;i<11;i++){
for(int j=1;j<11;j++){
row=i;low=j;
while(n<50){
if(a[row][low]==’U’){
row–;n++;
}
else if(a[row][low]==’L’){
low–;n++;
}
else if(a[row][low]==’R’){
low++;n++;
}
else if(a[row][low]==’D’){
row++;n++;
}
if(a[row][low]==’0′){
sum++;
break;
}
}
n=0;
}

}

System.out.println(sum);
scan.close();
}
}

 

/*
找出最短路径
0 1 0 0 0 0
0 0 0 1 0 0
0 1 0 0 0 1
1 0 0 0 1 0
0 0 1 1 0 0
1 0 0 0 0 0
*/
public class blue1 {
public static void main(String[] args) {
/*
迷宫找最优路径
*/
Scanner scan=new Scanner(System.in);
int N=scan.nextInt();
int M=scan.nextInt();
int MiGong[][]=GetMiGong(N,M);
int count=0;
boolean a=setWay(MiGong,0,0,count);
print(MiGong);
}
public static int[][] GetMiGong(int n,int m){
int number[][]=new int [n][m];
Scanner sc=new Scanner(System.in);
for(int i=0;i<n;i++){
for (int j = 0; j < m; j++) {
number[i][j]=sc.nextInt();
}
}
return number;
}
public static boolean setWay(int number[][],int x,int y,int count){
try{
int start=number[x][y];
int end=number[number.length-1][number[0].length-1];

if(end==2){
return true;
}
else{
if(number[x][y]==0){
number[x][y]=2;
count++;//用于控制最短路径
if(count%2==0) {
if (setWay(number, x + 1, y, count)) {
return true;
} else if (setWay(number, x, y + 1, count)) {
return true;
} else if (setWay(number, x – 1, y, count)) {
return true;
} else if (setWay(number, x, y – 1, count)) {
return true;
} else {
number[x][y] = 3;
return false;
}
}
else{
if (setWay(number, x , y+1, count)) {
return true;
} else if (setWay(number, x+1, y, count)) {
return true;
} else if (setWay(number, x – 1, y, count)) {
return true;
} else if (setWay(number, x, y – 1, count)) {
return true;
} else {
number[x][y] = 3;
return false;
}
}
}
else{
return false;
}
}
}
catch (ArrayIndexOutOfBoundsException e){

return false;
}
}
public static void print(int number[][]){
for(int i=0;i<number.length;i++){
for(int j=0;j<number[0].length;j++){
System.out.print(number[i][j]==3?0:number[i][j]);
System.out.print(” “);
}
System.out.println();
}
}

}

第二种解法:

暂时还没有实现,思路:可以用动态规划区实现!

 

 

 

 

 

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇