电路维修达达是来自异世界的魔女她在漫无目的地四处漂流的时候遇到了善良的少女翰翰从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障导致无法启动。电路板的整体结构是一个 R 行 C 列的网格R,C≤500如下图所示。每个格点都是电线的接点每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源右下角的接点接入飞行车的发动装置。达达发现因为某些元件的方向不小心发生了改变电路板可能处于断路的状态。她准备通过计算旋转最少数量的元件使电源与发动装置通过若干条短缆相连。不过电路的规模实在是太大了达达并不擅长编程希望你能够帮她解决这个问题。注意只能走斜向的线段水平和竖直线段不能走。输入格式输入文件包含多组测试数据。第一行包含一个整数 T表示测试数据的数目。对于每组测试数据第一行包含正整数 R 和 C表示电路板的行数和列数。之后 R 行每行 C 个字符字符是/和\中的一个表示标准件的方向。输出格式对于每组测试数据在单独的一行输出一个正整数表示所需的最小旋转次数。如果无论怎样都不能使得电源和发动机之间连通输出NO SOLUTION。数据范围1≤R,C≤500,1≤T≤5输入样例1 3 5 \\/\\ \\/// /\\\\输出样例1样例解释样例的输入对应于题目描述中的情况。只需要按照下面的方式旋转标准件就可以使得电源和发动机之间连通。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; import java.util.StringTokenizer; public class Main { static int N510,r,c; static char a[][]new char[N][N]; static int dist[][]new int[N][N]; static boolean f[][]new boolean[N][N]; static char g[]{\\,/,\\,/}; static int dx[]{-1,-1,1,1},dy[]{-1,1,1,-1};//格子可以向四个方向来进行扩展 static int ga[]{-1,-1,0,0},gb[]{-1,0,0,-1};//根据一个格点推出它的相邻的所有格子 ga表示横坐标的差值 gb表示纵坐标的差值。啊 static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { // StringTokenizer stnew StringTokenizer(br.readLine()); // int nInteger.parseInt(st.nextToken()); int tInteger.parseInt(br.readLine()); for (int i 0; i t; i) { StringTokenizer stnew StringTokenizer(br.readLine()); rInteger.parseInt(st.nextToken());cInteger.parseInt(st.nextToken()); for (int j 0; j r; j) { a[j]br.readLine().toCharArray(); } //每次变化的横坐标是1 -1 每次变化的纵坐标是1 -1 //不论哪种组合 都不会横纵坐标加起来和为奇数的点 if(((rc)1)1){//奇数点到不了 bw.write(NO SOLUTION\n); }else { bfs(); } } bw.flush(); bw.close(); bw.close(); } static void bfs() throws IOException{//双端队列 //假设在某一个点 可以向四个方向扩展 如果扩展的时候需要的形状和我有的形状是一样的 //那权值就是零 否则就是1 //如果是零那就插入到队头如果是一那就插入到队尾 //这个思路是根据迪杰斯特拉算法 每次距离短的总会被优先弹出 //队列中只会存在两种距离 假设我当前队列中有d和d1 两种距离 //弹出队头之后 它的距离可能从d变成d也可能从d变成d加一 前者权重是零后者权重是一 // 这时如果正在遍历的那条边的权重是0 加到队头如果是2我们加到队尾 //那此时队列中还是只有d和d1两种距离 //由此可以得出队列,在满足条件的情况下在任何时候都只有两种距离。 //最先找到的一定是最短的距离 这个问题相当于是迪杰斯特拉算法中边的权重只有零和一的问题 Dequeint[] dequenew LinkedList(); deque.add(new int[]{0,0}); for (int i 0; i N; i) { Arrays.fill(dist[i], Integer.MAX_VALUE); Arrays.fill(f[i],false);//记得重置 } dist[0][0]0; while(!deque.isEmpty()){ int no[]deque.poll(); int xno[0],yno[1]; if(!f[x][y]){ f[x][y]true; if(xr yc){ bw.write(dist[r][c]\n); break; } for (int i 0; i 4; i) { int nxxdx[i],nyydy[i]; if(nx0 || ny0 || nxr || nyc)continue; int nuxga[i],nvygb[i]; if(nu0 || nu0 || nur || nvc)continue; char cura[nu][nv]; int w((cur!g[i])?1:0); int disdist[x][y]w; if(dist[nx][ny]dis){ dist[nx][ny]dis; if(w0){ deque.addFirst(new int[]{nx,ny});//可能会重复入队 }else{ deque.addLast(new int[]{nx,ny}); } } } } } } }其实也可以直接用堆来进行上面的代码只是手动维护了一个有顺序的队列效率更高import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static int N510,r,c; static char a[][]new char[N][N]; static int dist[][]new int[N][N]; static boolean f[][]new boolean[N][N]; static char g[]{\\,/,\\,/}; static int dx[]{-1,-1,1,1},dy[]{-1,1,1,-1};//格子可以向四个方向来进行扩展 static int ga[]{-1,-1,0,0},gb[]{-1,0,0,-1};//根据一个格点推出它的相邻的所有格子 ga表示横坐标的差值 gb表示纵坐标的差值。啊 static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { // StringTokenizer stnew StringTokenizer(br.readLine()); // int nInteger.parseInt(st.nextToken()); int tInteger.parseInt(br.readLine()); for (int i 0; i t; i) { StringTokenizer stnew StringTokenizer(br.readLine()); rInteger.parseInt(st.nextToken());cInteger.parseInt(st.nextToken()); for (int j 0; j r; j) { a[j]br.readLine().toCharArray(); } //每次变化的横坐标是1 -1 每次变化的纵坐标是1 -1 //不论哪种组合 都不会横纵坐标加起来和为奇数的点 if(((rc)1)1){//奇数点到不了 bw.write(NO SOLUTION\n); }else { bfs(); } } bw.flush(); bw.close(); bw.close(); } static void bfs() throws IOException{//双端队列 //假设在某一个点 可以向四个方向扩展 如果扩展的时候需要的形状和我有的形状是一样的 //那权值就是零 否则就是1 //如果是零那就插入到队头如果是一那就插入到队尾 //这个思路是根据迪杰斯特拉算法 每次距离短的总会被优先弹出 //队列中只会存在两种距离 假设我当前队列中有d和d1 两种距离 //弹出队头之后 它的距离可能从d变成d也可能从d变成d加一 前者权重是零后者权重是一 // 这时如果正在遍历的那条边的权重是0 加到队头如果是2我们加到队尾 //那此时队列中还是只有d和d1两种距离 //由此可以得出队列,在满足条件的情况下在任何时候都只有两种距离。 //最先找到的一定是最短的距离 这个问题相当于是迪杰斯特拉算法中边的权重只有零和一的问题 //Dequeint[] dequenew LinkedList(); PriorityQueueint[] dequenew PriorityQueue((a,b)-a[2]-b[2]); deque.add(new int[]{0,0,0}); for (int i 0; i N; i) { Arrays.fill(dist[i], Integer.MAX_VALUE); Arrays.fill(f[i],false);//记得重置 } dist[0][0]0; while(!deque.isEmpty()){ int no[]deque.poll(); int xno[0],yno[1]; if(!f[x][y]){ f[x][y]true; if(xr yc){ bw.write(dist[r][c]\n); break; } for (int i 0; i 4; i) { int nxxdx[i],nyydy[i]; if(nx0 || ny0 || nxr || nyc)continue; int nuxga[i],nvygb[i]; if(nu0 || nu0 || nur || nvc)continue; char cura[nu][nv]; int w((cur!g[i])?1:0); int disdist[x][y]w; if(dist[nx][ny]dis){ dist[nx][ny]dis; deque.add(new int[]{nx,ny,dis}); } } } } } }字串变换已知有两个字串 A, B 及一组字串变换的规则至多 6 个规则:A1→B1A2→B2…规则的含义为在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2…。例如AabcdBxyz变换规则为abc→xuud→yy→yz则此时A 可以经过一系列的变换变为 B其变换的过程为abcd→xud→xy→xyz共进行了三次变换使得 A 变换为 B。注意一次变换只能变换一个子串例如 AaaBbb变换规则为a→b此时不能将两个a在一步中全部转换为b而应当分两步完成。输入格式输入格式如下A BA1 B1A2 B2… …第一行是两个给定的字符串 A 和 B。接下来若干行每行描述一组字串变换的规则。所有字符串长度的上限为 20。输出格式若在 10 步包含 10 步以内能将 A 变换为 B 则输出最少的变换步数否则输出NO ANSWER!。输入样例abcd xyz abc xu ud y y yz输出样例3代码1bfs超时import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set; import java.util.StringTokenizer; public class Main { static int N510,id; static String a[]new String[N]; static String b[]new String[N]; static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); // int nInteger.parseInt(st.nextToken()); String Ast.nextToken(),Bst.nextToken(); String line; while(((linebr.readLine())!null)!line.isEmpty()){ stnew StringTokenizer(line); a[id]st.nextToken(); b[id]st.nextToken(); } bfs(A,B); bw.flush(); bw.close(); bw.close(); } static void bfs(String A,String B) throws IOException{ QueueString[] queuenew LinkedListString[](); SetString setnew HashSet(); set.add(A); queue.add(new String[]{A,0}); while(!queue.isEmpty()){ String no[]queue.poll(); String stateno[0]; int stepInteger.parseInt(no[1]); if(B.equals(state)){ bw.write(step); return; }else if(step110){ for (int j 0; j state.length(); j) { for (int i 0; i id; i) { boolean fstate.substring(j).startsWith(a[i]); if(f){ String sonstate.substring(0,j)b[i]state.substring(ja[i].length()); if(set.contains(son))continue; else { queue.add(new String[]{son,step1}); set.add(son); } } } } } } bw.write(NO ANSWER!); } }代码2双向bfsimport java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int N510,id; static String a[]new String[N]; static String b[]new String[N]; static MapString, Integer map1new HashMap(); static MapString, Integer map2new HashMap(); static QueueString q1new LinkedList(); static QueueString q2new LinkedList(); static BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); // int nInteger.parseInt(st.nextToken()); String Ast.nextToken(),Bst.nextToken(); if(A.equals(B)){ System.out.println(0); return; } String line; while(((linebr.readLine())!null)!line.isEmpty()){ stnew StringTokenizer(line); a[id]st.nextToken(); b[id]st.nextToken(); } bfs(A,B); bw.flush(); bw.close(); bw.close(); } static void bfs(String A,String B) throws IOException{ q1.add(A);map1.put(A, 0); q2.add(B);map2.put(B, 0); while(!q1.isEmpty() !q2.isEmpty()){ if(q1.size()q2.size()){ int resextend1(); if(res!-1){//返回值不为-1 说明找到了解 否则本层已经超出了范围 就找不到解 return; } }else{ int resextend2(); if(res!-1){ return; } } } bw.write(NO ANSWER!); } static int extend1() throws IOException{ int curq1.size();//每次扩展的时候 不能只是扩展一个 而是要扩展一层 //因为每次都会把一层的结点全部弹出 所以cur刚好是一层的数量 while(cur--0){ String uq1.poll(); int stepmap1.get(u); if(step110)continue;//无效的可以跳过 但不可return 因为同一层其他节点还可以扩展 for (int i 0; i id; i) { for (int j 0; j u.length()-a[i].length(); j) { if(u.substring(j, ja[i].length()).startsWith(a[i])){ String sonu.substring(0,j)b[i]u.substring(ja[i].length()); if(map2.containsKey(son)){ bw.write(step1map2.get(son)); return step1map2.get(son); } if(map1.containsKey(son))continue; else { q1.add(son); map1.put(son, step1); } } } } } return -1; } static int extend2() throws IOException{ int curq2.size(); while(cur--0){ String uq2.poll(); int stepmap2.get(u); if(step110)continue; for (int i 0; i id; i) { for (int j 0; j u.length()-b[i].length(); j) { if(u.substring(j, jb[i].length()).startsWith(b[i])){ String sonu.substring(0,j)a[i]u.substring(jb[i].length()); if(map1.containsKey(son)){ bw.write(step1map1.get(son)); return step1map1.get(son); } if(map2.containsKey(son))continue; else { q2.add(son); map2.put(son, step1); } } } } } return -1; } }