企业官网建设流程全解析

电路维修

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。

有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个 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 N=510,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 br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { // StringTokenizer st=new StringTokenizer(br.readLine()); // int n=Integer.parseInt(st.nextToken()); int t=Integer.parseInt(br.readLine()); for (int i = 0; i < t; i++) { StringTokenizer st=new StringTokenizer(br.readLine()); r=Integer.parseInt(st.nextToken());c=Integer.parseInt(st.nextToken()); for (int j = 0; j < r; j++) { a[j]=br.readLine().toCharArray(); } //每次变化的横坐标是+1 -1 每次变化的纵坐标是+1 -1 //不论哪种组合 都不会横纵坐标加起来和为奇数的点 if(((r+c)&1)==1){//奇数点到不了 bw.write("NO SOLUTION\n"); }else { bfs(); } } bw.flush(); bw.close(); bw.close(); } static void bfs() throws IOException{//双端队列 //假设在某一个点 可以向四个方向扩展 如果扩展的时候需要的形状和我有的形状是一样的 //那权值就是零 否则就是1 //如果是零，那就插入到队头，如果是一，那就插入到队尾 //这个思路是根据迪杰斯特拉算法 每次距离短的总会被优先弹出 //队列中只会存在两种距离 假设我当前队列中有d和d+1 两种距离 //弹出队头之后 它的距离可能从d变成d，也可能从d变成d加一 前者权重是零，后者权重是一 // 这时如果正在遍历的那条边的权重是0 加到队头，如果是2，我们加到队尾 //那此时队列中还是只有d和d+1两种距离 //由此可以得出队列,在满足条件的情况下，在任何时候都只有两种距离。 //最先找到的一定是最短的距离 这个问题相当于是迪杰斯特拉算法中边的权重只有零和一的问题 Deque<int[]> deque=new 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 x=no[0],y=no[1]; if(!f[x][y]){ f[x][y]=true; if(x==r && y==c){ bw.write(dist[r][c]+"\n"); break; } for (int i = 0; i < 4; i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx<0 || ny<0 || nx>r || ny>c)continue; int nu=x+ga[i],nv=y+gb[i]; if(nu<0 || nu<0 || nu>=r || nv>=c)continue; char cur=a[nu][nv]; int w=((cur!=g[i])?1:0); int dis=dist[x][y]+w; if(dist[nx][ny]>dis){ dist[nx][ny]=dis; if(w==0){ 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 N=510,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 br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { // StringTokenizer st=new StringTokenizer(br.readLine()); // int n=Integer.parseInt(st.nextToken()); int t=Integer.parseInt(br.readLine()); for (int i = 0; i < t; i++) { StringTokenizer st=new StringTokenizer(br.readLine()); r=Integer.parseInt(st.nextToken());c=Integer.parseInt(st.nextToken()); for (int j = 0; j < r; j++) { a[j]=br.readLine().toCharArray(); } //每次变化的横坐标是+1 -1 每次变化的纵坐标是+1 -1 //不论哪种组合 都不会横纵坐标加起来和为奇数的点 if(((r+c)&1)==1){//奇数点到不了 bw.write("NO SOLUTION\n"); }else { bfs(); } } bw.flush(); bw.close(); bw.close(); } static void bfs() throws IOException{//双端队列 //假设在某一个点 可以向四个方向扩展 如果扩展的时候需要的形状和我有的形状是一样的 //那权值就是零 否则就是1 //如果是零，那就插入到队头，如果是一，那就插入到队尾 //这个思路是根据迪杰斯特拉算法 每次距离短的总会被优先弹出 //队列中只会存在两种距离 假设我当前队列中有d和d+1 两种距离 //弹出队头之后 它的距离可能从d变成d，也可能从d变成d加一 前者权重是零，后者权重是一 // 这时如果正在遍历的那条边的权重是0 加到队头，如果是2，我们加到队尾 //那此时队列中还是只有d和d+1两种距离 //由此可以得出队列,在满足条件的情况下，在任何时候都只有两种距离。 //最先找到的一定是最短的距离 这个问题相当于是迪杰斯特拉算法中边的权重只有零和一的问题 //Deque<int[]> deque=new LinkedList<>(); PriorityQueue<int[]> deque=new 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 x=no[0],y=no[1]; if(!f[x][y]){ f[x][y]=true; if(x==r && y==c){ bw.write(dist[r][c]+"\n"); break; } for (int i = 0; i < 4; i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx<0 || ny<0 || nx>r || ny>c)continue; int nu=x+ga[i],nv=y+gb[i]; if(nu<0 || nu<0 || nu>=r || nv>=c)continue; char cur=a[nu][nv]; int w=((cur!=g[i])?1:0); int dis=dist[x][y]+w; if(dist[nx][ny]>dis){ dist[nx][ny]=dis; deque.add(new int[]{nx,ny,dis}); } } } } } }

字串变换

已知有两个字串 A, B 及一组字串变换的规则（至多 6 个规则）:

A1→B1

A2→B2

…

规则的含义为：在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2…。

例如：A＝abcdB＝xyz

变换规则为：

abc→xuud→yy→yz

则此时，A 可以经过一系列的变换变为 B，其变换的过程为：

abcd→xud→xy→xyz

共进行了三次变换，使得 A 变换为 B。

注意，一次变换只能变换一个子串，例如 A＝aaB＝bb

变换规则为：

a→b

此时，不能将两个a在一步中全部转换为b，而应当分两步完成。

输入格式

输入格式如下：

A B
A1 B1
A2 B2
… …

第一行是两个给定的字符串 A 和 B。

接下来若干行，每行描述一组字串变换的规则。

所有字符串长度的上限为 20。

输出格式

若在 10 步（包含 10 步）以内能将 A 变换为 B ，则输出最少的变换步数；否则输出NO ANSWER!。

输入样例：

abcd xyz abc xu ud y y yz

输出样例：

3

代码1（bfs超时）

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 N=510,id; static String a[]=new String[N]; static String b[]=new String[N]; static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); // int n=Integer.parseInt(st.nextToken()); String A=st.nextToken(),B=st.nextToken(); String line; while(((line=br.readLine())!=null)&&!line.isEmpty()){ st=new 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{ Queue<String[]> queue=new LinkedList<String[]>(); Set<String> set=new HashSet<>(); set.add(A); queue.add(new String[]{A,"0"}); while(!queue.isEmpty()){ String no[]=queue.poll(); String state=no[0]; int step=Integer.parseInt(no[1]); if(B.equals(state)){ bw.write(step+""); return; }else if(step+1<=10){ for (int j = 0; j < state.length(); j++) { for (int i = 0; i < id; i++) { boolean f=state.substring(j).startsWith(a[i]); if(f){ String son=state.substring(0,j)+b[i]+state.substring(j+a[i].length()); if(set.contains(son))continue; else { queue.add(new String[]{son,step+1+""}); set.add(son); } } } } } } bw.write("NO ANSWER!"); } }

代码2（双向bfs）

import 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 N=510,id; static String a[]=new String[N]; static String b[]=new String[N]; static Map<String, Integer> map1=new HashMap<>(); static Map<String, Integer> map2=new HashMap<>(); static Queue<String> q1=new LinkedList<>(); static Queue<String> q2=new LinkedList<>(); static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); // int n=Integer.parseInt(st.nextToken()); String A=st.nextToken(),B=st.nextToken(); if(A.equals(B)){ System.out.println(0); return; } String line; while(((line=br.readLine())!=null)&&!line.isEmpty()){ st=new 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 res=extend1(); if(res!=-1){//返回值不为-1 说明找到了解 否则本层已经超出了范围 就找不到解 return; } }else{ int res=extend2(); if(res!=-1){ return; } } } bw.write("NO ANSWER!"); } static int extend1() throws IOException{ int cur=q1.size();//每次扩展的时候 不能只是扩展一个 而是要扩展一层 //因为每次都会把一层的结点全部弹出 所以cur刚好是一层的数量 while(cur-->0){ String u=q1.poll(); int step=map1.get(u); if(step+1>10)continue;//无效的可以跳过 但不可return 因为同一层其他节点还可以扩展 for (int i = 0; i < id; i++) { for (int j = 0; j <= u.length()-a[i].length(); j++) { if(u.substring(j, j+a[i].length()).startsWith(a[i])){ String son=u.substring(0,j)+b[i]+u.substring(j+a[i].length()); if(map2.containsKey(son)){ bw.write(step+1+map2.get(son)+""); return step+1+map2.get(son); } if(map1.containsKey(son))continue; else { q1.add(son); map1.put(son, step+1); } } } } } return -1; } static int extend2() throws IOException{ int cur=q2.size(); while(cur-->0){ String u=q2.poll(); int step=map2.get(u); if(step+1>10)continue; for (int i = 0; i < id; i++) { for (int j = 0; j <= u.length()-b[i].length(); j++) { if(u.substring(j, j+b[i].length()).startsWith(b[i])){ String son=u.substring(0,j)+a[i]+u.substring(j+b[i].length()); if(map1.containsKey(son)){ bw.write(step+1+map1.get(son)+""); return step+1+map1.get(son); } if(map2.containsKey(son))continue; else { q2.add(son); map2.put(son, step+1); } } } } } return -1; } }