Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

晕圈了,大家看看3009题这么做为啥出错

Posted by TheIllsionist at 2017-11-04 13:07:08
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator