AcWing 845. java同学(注释详解)
原题链接
中等
作者:
季之秋
,
2021-01-15 18:16:15
,
所有人可见
,
阅读 962
java代码
import java.util.*;
import java.io.*;
public class Main{
static void swap(char c[],int a,int b){//用于交换值来变换状态
char s=c[a];
c[a]=c[b];
c[b]=s;
}
static int bfs(String start,String end){
Queue<String> q=new LinkedList<>();//存储所有状态
Map<String,Integer> map=new HashMap<>();//存储每个状态得交换次数
q.offer(start); map.put(start,0);//存初始状态
int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0};//四个方向
while(!q.isEmpty()){//枚举所有状态
String t=q.poll();//取出头一个状态并向前寻找(t过程中不能修改,因为有四次变化 而位置都是map[t]+1)
if(t.equals(end)) return map.get(t);//直到找到结束状态为止,此时因为临近扩散原理所以一定是最小值;
int k=t.indexOf('x');//找到x的坐标
int x=k/3,y=k%3;//将一维下标转二维坐标利于上下左右改变状态
for(int i=0;i<4;i++){//每个状态都有四次变化
int a=x+dx[i],b=y+dy[i];//变化状态之后x的下标
if(a>=0&&a<3&&b>=0&&b<3){//变化后不出界就是可用的
char arr[]=t.toCharArray();//字符串里面不能交换所以就到字符数组里,不直接修改t(以便后续的次数存储直接+1)
swap(arr,k,a*3+b);//交换值&变状态(因为前面是一维存储字符串,所以二维坐标转一维下标)
String s=new String(arr);//转成字符串,因为定义队列和map是用String的
if(map.get(s)==null){//如果这个状态没出现过就存储这个状态
q.offer(s);
map.put(s,map.get(t)+1);//变化前的次数值加一,因为是+1所以保证四个方向变化的值都是一样的;
}
}
}
}
return -1;
}
public static void main(String[] args)throws Exception{
BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
String q[]=sc.readLine().split(" ");
String start="";//因为输入问题所以不能直接给一个字符串
for(int i=0;i<q.length;i++){
start+=q[i];
}
String end="12345678x";
System.out.println(bfs(start,end));//从开始状态到结束状态要多少次交换
}
}
为什么只写一个swap呢
我知道了,这里用临时数组arr来接受t的字符串数组了,更改的是arr的值,t的值没有改变,所以不用恢复现场
pool()哪来的,队列没有pool()方法吧
orz
这个swap我想了半天,刚开始想用String的replace,一直行不通,直到看到你的toCharArray,恍然大悟
还有一个问题是交换过去了不用再交换回来吗
太细了,终于看懂了
为什么swap会交换数组元素值呢,不是仅仅是值传递吗?
因为我们交换的是我们传递过去的数组内的两个值(方法的第一个数组参数)