ブルーブリッジカップ-カードシフト(java)
12934 ワード
カードシフト
華容道のゲームをしたことがありますか.これは似ていますが、もっと簡単なゲームです.下の3 x 2の格子を見て
+—+—+—+ | A | * | * | +—+—+—+ | B | | * | +—+—+—+
その中に5枚の札を置いて、そのうちAは関羽を代表して、Bは張飛を代表して、*は兵士を代表します.もう一つの格子は空いています.
1枚のカードを隣接するスペースに移動することができます(対角は隣接しません).ゲームの目的は関羽と張飛が位置を交換し、他のカードはどこでも構いません.
入力フォーマット:2行6文字を入力して現在の状況を表す
出力フォーマット:1つの整数、最低のどのくらいのステップを表して、やっとABを変位することができます(他のカードの位置は勝手にします)
たとえば、入力:*A**B
プログラム出力:17
たとえば、入力:A B***
プログラム出力:12
リソース約定:ピークメモリ消費<256 M CPU消費<1000 ms
要求通りに出力し、「入力してください」のような余分な内容を蛇足せずに印刷してください.
すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.
注意:main関数は0を返す必要があります注意:ANSI C/ANSI C++標準のみを使用し、コンパイル環境やオペレーティングシステムに依存する特殊な関数を呼び出さないでください.注意:すべての依存する関数は、ソースファイル内のincludeで明確にする必要があります.通常のヘッダファイルは、エンジニアリング設定で省略することはできません.
コミットするときは、目的のコンパイラタイプを選択することに注意してください.
華容道のゲームをしたことがありますか.これは似ていますが、もっと簡単なゲームです.下の3 x 2の格子を見て
+—+—+—+ | A | * | * | +—+—+—+ | B | | * | +—+—+—+
その中に5枚の札を置いて、そのうちAは関羽を代表して、Bは張飛を代表して、*は兵士を代表します.もう一つの格子は空いています.
1枚のカードを隣接するスペースに移動することができます(対角は隣接しません).ゲームの目的は関羽と張飛が位置を交換し、他のカードはどこでも構いません.
入力フォーマット:2行6文字を入力して現在の状況を表す
出力フォーマット:1つの整数、最低のどのくらいのステップを表して、やっとABを変位することができます(他のカードの位置は勝手にします)
たとえば、入力:*A**B
プログラム出力:17
たとえば、入力:A B***
プログラム出力:12
リソース約定:ピークメモリ消費<256 M CPU消費<1000 ms
要求通りに出力し、「入力してください」のような余分な内容を蛇足せずに印刷してください.
すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.
注意:main関数は0を返す必要があります注意:ANSI C/ANSI C++標準のみを使用し、コンパイル環境やオペレーティングシステムに依存する特殊な関数を呼び出さないでください.注意:すべての依存する関数は、ソースファイル内のincludeで明確にする必要があります.通常のヘッダファイルは、エンジニアリング設定で省略することはできません.
コミットするときは、目的のコンパイラタイプを選択することに注意してください.
import java.util.*;
public class KaPianHuanWei {
static Queue q = new LinkedList();
static int Pos_a_x = -1, Pos_a_y = -1;
static int Pos_b_x = -1, Pos_b_y = -1;
// static Pos sign = new Pos(-1,-1);
static int[][] arr = {{-1,0},{1,0},{0,-1},{0,1}};
public static void main(String[] args) throws InterruptedException {
String[][] str = new String[2][3];
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 2; i++) {
String temp = sc.nextLine();
for (int j = 0; j < 3; j++) {
str[i][j] = temp.substring(j, j+1);
if(str[i][j].equals("A")){Pos_a_x = i; Pos_a_y = j;}
if(str[i][j].equals("B")){Pos_b_x = i; Pos_b_y = j;}
}
}
sc.close();
long start = System.currentTimeMillis();
Pos result = null;
q.add(new Pos(0,str));
while(!q.isEmpty()){
Pos t = q.remove();
if(finish(t.str)){ result = t; break;}
else{
move(t);
}
}
System.out.println(result.step);
// System.out.println(result.s);
long end = System.currentTimeMillis();
System.out.println(" :"+(end-start)+"ms");
}
public static void move(Pos p) throws InterruptedException{
String[][] t = p.str;
for (int i= 0; i< 2; i++) {
for (int j = 0; j < 3; j++) {
if(t[i][j].equals(" ")){
if(i-1>=0 && (i-1!=p.x || j!=p.y)){
String[][] temp = new String[2][3];
copy(t, temp);
temp = swap(temp,i,j,i-1,j);
q.add(new Pos(i,j,p.step+1,temp,p.s+"->"+t[i-1][j]));
// p(temp);
}
if(i+1<=1 && (i+1!=p.x || j!=p.y)){
String[][] temp = new String[2][3];
copy(t, temp);
temp = swap(temp,i,j,i+1,j);
q.add(new Pos(i,j,p.step+1,temp,p.s+"->"+t[i+1][j]));
// p(temp);
}
if(j-1>=0 && (i!=p.x || j-1!=p.y)){
String[][] temp = new String[2][3];
copy(t, temp);
temp = swap(temp,i,j,i,j-1);
q.add(new Pos(i,j,p.step+1,temp,p.s+"->"+t[i][j-1]));
// p(temp);
}
if(j+1<=2 && (i!=p.x || j+1!=p.y)){
String[][] temp = new String[2][3];
copy(t, temp);
temp = swap(temp,i,j,i,j+1);
q.add(new Pos(i,j,p.step+1,temp,p.s+"->"+t[i][j+1]));
// p(temp);
}
}
}
}
}
public static void copy(String[][] src,String[][] dis){
for (int i = 0; i < src.length; i++) {
for (int j = 0; j < src[i].length; j++) {
dis[i][j] = src[i][j];
}
}
}
public static String[][] swap(String[][] s,int i,int j,int x,int y){
String t = s[i][j];
s[i][j] = s[x][y];
s[x][y] = t;
return s;
}
public static boolean finish(String[][] str){
int count = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
if(str[i][j].equals("A") && i==Pos_b_x && j==Pos_b_y) count++;
if(str[i][j].equals("B") && i==Pos_a_x && j==Pos_a_y) count++;
}
}
if(count == 2)return true;
return false;
}
// public static void p(String[][] s) throws InterruptedException{
// for (int i = 0; i < s.length; i++) {
// for (int j = 0; j < s[i].length; j++) {
// System.out.print(s[i][j]);
// }
// System.out.println();
// }
// System.out.println();
// Thread.sleep(500);
// }
}
class Pos{
int x = -1;
int y = -1;
int step;
String s = "";
String[][] str = new String[2][3];
public Pos() {
}
public Pos(int step, String[][] str) {
super();
this.step = step;
this.str = str;
}
public Pos(int x, int y, int step, String[][] str,String s) {
super();
this.x = x;
this.y = y;
this.step = step;
this.str = str;
this.s = s;
}
}