题目描述
达达是来自异世界的魔女,她在漫无目的地四处漂流的时候,遇到了善良的少女翰翰,从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障,导致无法启动。
电路板的整体结构是一个R行C列的网格(R,C≤500),如下图所示。
电路.png
每个格点都是电线的接点,每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后,它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源,右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变,电路板可能处于断路的状态。
她准备通过计算,旋转最少数量的元件,使电源与发动装置通过若干条短缆相连。
不过,电路的规模实在是太大了,达达并不擅长编程,希望你能够帮她解决这个问题。
注意:只能走斜向的线段,水平和竖直线段不能走。
样例
1
3 5
\\/\\
\\///
/\\\\
算法1
(BFS + 双端队列) $O(n)$
Java 代码
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = 710, M = N * N, n, m, dep[][];
static char g[][];
static Pair q[];
static boolean book[][];
public static void main(String[] args) throws IOException {
int t = readInt();
g = new char[N][N];
q = new Pair[M*2];
dep = new int[N][N];
book = new boolean[N][N];
while (t-- > 0) {
n = readInt();
m = readInt();
for (int i = 0; i < n; i++) {
String temp = readLine();
for (int j = 0; j < m; j++) {
g[i][j] = temp.charAt(j);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dep[i][j] = 0x3f3f3f3f;
}
}
if ((n + m) % 2 == 1) {
System.out.println("NO SOLUTION");
} else {
bfs();
System.out.println(dep[n][m]);
}
}
}
static int ne[][] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
static int ne2[][] = {{0, 0}, {0, -1}, {-1, 0}, {-1, -1}};
static void bfs() {
book = new boolean[N][N];
int hh = M, tt = M;
dep[0][0] = 0;
q[M] = new Pair(0, 0);
while (hh <= tt) {
Pair p = q[hh++];
if (p.x == n && p.y == m) {
return;
}
if (book[p.x][p.y]) continue;
book[p.x][p.y] = true;
for (int i = 0; i < 4; i++) {
int a = p.x + ne[i][0], b = p.y + ne[i][1];
int tx = p.x + ne2[i][0], ty = p.y + ne2[i][1];
if (a < 0 || a > n || b < 0 || b > m) continue;
if ((i == 1 || i == 2) && g[tx][ty] == '/' || (i == 0 || i == 3) && g[tx][ty] == '\\') {
q[--hh] = new Pair(a, b);
dep[a][b] = Math.min(dep[a][b], dep[p.x][p.y]);
} else {
q[++tt] = new Pair(a, b);
dep[a][b] = Math.min(dep[a][b], dep[p.x][p.y] + 1);
}
}
}
}
static class Pair {
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine().trim());
return st.nextToken();
}
static long readLong() throws IOException {
return Long.parseLong(next());
}
static int readInt() throws IOException {
return Integer.parseInt(next());
}
static double readDouble() throws IOException {
return Double.parseDouble(next());
}
static char readCharacter() throws IOException {
return next().charAt(0);
}
static String readLine() throws IOException {
return br.readLine().trim();
}
}