| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
晕圈了,大家看看3009题这么做为啥出错import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner input = new Scanner(System.in);
while(true){
int W = input.nextInt();
int H = input.nextInt();
if(W == 0 && H == 0){
break;
}
int[][] squares = new int[H][W];
int sh = -1,sw = -1;
for(int i = 0;i < H;i++){
for(int j = 0;j < W;j++){
squares[i][j] = input.nextInt();
if(squares[i][j] == 2){
sh = i;
sw = j;
}
}
}
squares[sh][sw] = 0;
int result = startMove2(sh,sw,0,squares);
System.out.println(result > 10 ? -1 : result);
}
}
public static int startMove2(int h,int w,int steps,int[][] squares){
int[] dh = new int[]{-1,0,1,0};
int[] dw = new int[]{0,-1,0,1};
boolean canStart = false; //是否可有效开始移动
int[] dirRes = new int[4]; //记录上、左、下、右四个方向最小结果
Arrays.fill(dirRes,-1);
int relRes = Integer.MAX_VALUE;
for(int i = 0;i < 4;i++){
int th = h + dh[i];
int tw = w + dw[i];
if(th >= 0 && th < squares.length && tw >= 0 && tw < squares[0].length && squares[th][tw] != 1){
canStart = true; //可有效开始移动
dirRes[i] = move2(th,tw,i,1,squares); //只可能返回-1或大于0的值
}
}
//不能有效开始移动 或 向各个方向移动都无法到达目标
if(!canStart || (dirRes[0]==dirRes[1] && dirRes[1]==dirRes[2] && dirRes[2]==dirRes[3] && dirRes[0]==-1))
return -1;
else{
for(int i = 0;i < 4;i++){
if(dirRes[i] != -1){
relRes = Math.min(relRes,dirRes[i]);
}
}
}
return relRes;
}
public static int move2(int h,int w,int ld,int steps,int[][] squares){
//超过限制步数或者走出界限都不成功
if(steps > 10 || (h < 0 || h >= squares.length || w < 0 || w >= squares[0].length))
return -1;
int[] dirRes = new int[4];
int result = Integer.MAX_VALUE;
int[] dh = new int[]{-1,0,1,0};
int[] dw = new int[]{0,-1,0,1};
if(squares[h][w] == 3) //走到目标
return steps;
else if(squares[h][w] == 0) //无任何改变
return move2(h + dh[ld],w + dw[ld],ld,steps,squares);
else{
squares[h][w] = 0; //在递归前修改状态
for(int i = 0;i < 4;i++){
dirRes[i] = move2(h - dh[ld],w - dw[ld],i,steps + 1,squares);
}
squares[h][w] = 1; //递归后改回状态
if(dirRes[0]==dirRes[1] && dirRes[1]==dirRes[2] && dirRes[2]==dirRes[3] && dirRes[0]==-1)
return -1;
else{
for (int i = 0;i < 4;i++){
if(dirRes[i] != -1){
result = Math.min(result,dirRes[i]);
}
}
}
return result;
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator