これだけで私のくじけを記念するすごいアルゴリズムです.

5023 ワード

これだけで私のくじけを記念するすごいアルゴリズムです.
これは私の第一編で、オンライン筆記試験で、軽蔑というのはもっと適当だと思います.本気で自分のアルゴリズムがだめになったと思います.でも遠方はやはり激情のを満たして、更にくじけても前進しますよね!
問題
a 8 b 8 c 8 d 8 f 8 g 8 h 8 b 7 c 7 d 7 f 7 g 7 h 7 b 6 c 6 d 6 d 6 f 6 g 6 f 6 h 6 f 6 h 6 f 6 f 6 h 6 f 6 f 6 f 6 f 5 f 5 g 5 h 5 h 5 b 4 c 4 d 4 f 4 g 4 h 4 f 4 f 4 f 3 b 3 c 3 c 3 d 3 f 3 f 3 g 3 f 1 f 1 f 1 f 1 f 2 f 1 f 1 f 1 f 1 f 1 f 1 f 2 f 1 f 2 f 2 f 2 f 3 f 3 f 1 f 3 f 3 f 3 f 1 f 1 f 2 f 1 f 1 f 3 f 3 f 1 f 3 f 3 f 3 f 3 f 3 f 1 f 1 f 3 f 3 f
説明
この一ブロックの皿の中で、一つの点からもう一つの点までの最短距離を探します.テーマは対角線のブロックを歩く時、対角線のL、R、U、D、LU、LD、RU、RDそれぞれに対応する方向は左、右、上、左、左下、左下、左下、右上です.右下入力形式:1行目は起点2行目は終点出力結果:1行目は歩くステップ数n残りのn行は1回移動する方向です.
入出力の例:
a 8 h 1 7 RD RD RD
策略
まず入力された座標記号を座標数に変換し、現在の所在点と終点座標の対比に基づいて移動方法を判断します.x、y座標が等しくない限り、xをします.yは同時にビットを変えます.XまたはYだけが違ったら、1ビットを移動します.現在点は終点X、Y座標と等しくなったら、最短パスを見つけます.
コード
public class Main {

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int curX = 0; //   X  
    int curY = 0; //   Y  
    int dstX = 0; //   X  
    int dstY = 0; //   Y  
    int tag = 0; //              (1:    ,0:    )
    int stepCount = 0; //   

    //          
    ArrayList step = new ArrayList();
    while (in.hasNextLine()) {
        String inStr = in.nextLine();
        tag++;

        if (tag == 1) {
            //                ,  :a8 -> 97,56
            curX = inStr.charAt(0);
            curY = inStr.charAt(1);

        } else {
            tag = 0;
            dstX = inStr.charAt(0);
            dstY = inStr.charAt(1);

            //               ArrayList,        
            step.clear();
            stepCount = 0;

            //           
            while (curX != dstX || curY != dstY) {
                //            
                if (curX >= dstX && curY >= dstY) {

                    if (curX != dstX && curY != dstY) {
                        curX--;
                        curY--;
                        step.add("LD");
                        stepCount++;
                    } else if (curX == dstX && curY != dstY) {
                        curY--;
                        step.add("D");
                        stepCount++;
                    } else if (curX != dstX && curY == dstY) {
                        curX--;
                        step.add("L");
                        stepCount++;
                    }

                    continue;
                }
                //            
                else if (curX >= dstX && curY <= dstY) {
                    if (curX != dstX && curY != dstY) {
                        curX--;
                        curY++;
                        step.add("LU");
                        stepCount++;
                    } else if (curX == dstX && curY != dstY) {
                        curY++;
                        step.add("U");
                        stepCount++;
                    } else if (curX != dstX && curY == dstY) {
                        curX--;
                        step.add("L");
                        stepCount++;
                    }

                }
                //            
                else if (curX <= dstX && curY >= dstY) {
                    if (curX != dstX && curY != dstY) {
                        curX++;
                        curY--;
                        step.add("RD");
                        stepCount++;
                    } else if (curX == dstX && curY != dstY) {
                        curY--;
                        step.add("D");
                        stepCount++;
                    } else if (curX != dstX && curY == dstY) {
                        curX++;
                        step.add("R");
                        stepCount++;
                    }

                }
                //            
                else if (curX <= dstX && curY <= dstY) {
                    if (curX != dstX && curY != dstY) {
                        curX++;
                        curY++;
                        step.add("RU");
                        stepCount++;
                    } else if (curX == dstX && curY != dstY) {
                        curY++;
                        step.add("U");
                        stepCount++;
                    } else if (curX != dstX && curY == dstY) {
                        curX++;
                        step.add("R");
                        stepCount++;
                    }

                }

            }
            /*
             *                  
             */
            System.out.println(stepCount);
            for (int i = 0, s = step.size(); i < s; i++) {
                System.out.println(step.get(i));
            }
        }

    }
    in.close();
}
}