AcWing 3156. 卡片换位 可修改行列
原题链接
简单
作者:
季之秋
,
2021-04-02 16:48:29
,
所有人可见
,
阅读 385
import java.util.*;
public class Main{
static String start = "";
static int a,b ;
static int n = 2 , m = 3 ; // 可修改行数列数 ,自行测试,
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
for(int i=0;i<n;i++){
start += sc.nextLine();
for(int j=0;j<m;j++){
if( start.charAt((i*m)+j) == 'A' ) a = i*m+j;
if( start.charAt((i*m)+j) == 'B' ) b = i*m+j;
}
}
System.out.println(bfs());
}
static int dx[] = {0,-1,0,1};
static int dy[] = {1,0,-1,0};
static int bfs(){
Queue<String> q = new LinkedList<>();
HashMap<String,Integer> map = new HashMap();
map.put(start, 0);
q.add(start);
while(!q.isEmpty()){
String s = q.poll();
int d = map.get(s);
if(s.indexOf('B') == a && s.indexOf('A') == b){
return d;
}
int index = s.indexOf(" ");
int sx = index / m;
int sy = index % m;
for(int i=0;i<4;i++){
int x = sx+dx[i], y = sy+dy[i];
if(x<0 || y<0 || x>=n || y>=m ) continue;
String str = swap(s, index, x*m+y);
if(map.get(str) == null){
map.put(str, d+1);
q.add(str);
}
}
}
return -1;
}
static String swap(String str, int i, int j){
char c[] = str.toCharArray();
char ch = c[i];
c[i] = c[j];
c[j] = ch;
return new String(c);
}
}