描述
Ha'nyu是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女Rika，从而被收留在地球上。Rika的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法启动。
电路板的整体结构是一个R行C列的网格（R,C≤500），如右图所示。每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
Ha'nyu发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。不过，电路的规模实在是太大了，Ha'nyu并不擅长编程，希望你能够帮她解决这个问题。
输入格式
输入文件包含多组测试数据。第一行包含一个整数T 表示测试数据的数目。
对于每组测试数据，第一行包含正整数R 和C，表示电路板的行数和列数。
之后R 行，每行C 个字符，字符是"/"和""中的一个，表示标准件的方向。
输出格式
对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。
样例输入
1
3 5
/
///
/\
样例输出
1
数据范围与约定
对于40% 的数据，R,C≤5。
对于100% 的数据，R,C≤500，T≤5。
样例解释
样例的输入对应于题目描述中的情况。
只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。
来源
杜宇飞，石家庄二中【Nescafé 5】杯NOIP模拟赛
思路:考虑BFS,从左上角开始搜索,显然当边长一奇一偶时无法走到右下角,且左上 右下角一定为''.则可以按照每个格子保存的斜线方向往当前格子的四周bfs,判断是否需要改变.用介质为当前旋转次数的优先队列维护BFS即可
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define rg register
#define LL long long
#define __space putchar(' ')
#define __endl putchar('
')
template <typename qwq> inline void read(qwq & x)
{
x = 0;
rg int f = 1;
rg char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
x *= f;
}
template <typename qaq> inline void print(qaq x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
char Map[2333][2333];
int n,m,t;
int ans[2333][2333];
int dx[] = {0,0,1,1,0,-1,-1,-1,1};
int dy[] = {0,1,0,1,-1,0,-1,1,-1};
//1:右 2:下 3:右下 4:左 5:上 6:左上 7:右上 8:左下
struct node
{
int w,x,y;
char c;
friend bool operator < (const node a,const node b)
{
return a.w > b.w;
}
}start;
priority_queue<node>heap;
//first:cost second:point
inline void prework()
{
while(!heap.empty()) heap.pop();
for (rg int i = 1;i <= n;++i)
{
for (rg int j = 1;j <= m;++j)
{
ans[i][j] = 0x7f7f7f7f;
}
}
ans[1][1] = 0;
}
#define you 1
#define xia 2
#define youxia 3
#define zuo 4
#define shang 5
#define zuoshang 6
#define youshang 7
#define zuoxia 8
inline void boy_friend_search()
{
heap.push(start);
while (!heap.empty())
{
rg node now = heap.top();
rg int x = now.x,y = now.y;
rg char c = now.c;
heap.pop();
for (rg int i = 1;i <= 8;++i)
{
rg int nx = x + dx[i],ny = y + dy[i];
rg char nc;
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (i == zuo || i == you || i == shang || i == xia)// 向左/右/上/下走
{
if (c == Map[nx][ny])//如果两个相同的话
{
//若要保证联通则必须更改
if (ans[x][y] + 1 < ans[nx][ny])
{
ans[nx][ny] = ans[x][y] + 1;
// nc = (Map[x][y] == '/') ? 92 : '/';
if (c == '/') nc = 92;
else nc = '/';
if (nx == n && ny == m) return;
heap.push((node) {ans[nx][ny],nx,ny,nc});
}
}
else
{
//否则不需要更改
if (ans[x][y] < ans[nx][ny])
{
ans[nx][ny] = ans[x][y];
if (nx == n && ny == m) return;
heap.push((node) {ans[nx][ny],nx,ny,Map[nx][ny]});
}
}
}
else if (i == zuoshang || i == youxia)//向 左上/右下
{
if (c == '/') continue;
if (c != Map[nx][ny])//如果两个不同的话
{
//若要保证联通则必须更改
if (ans[x][y] + 1 < ans[nx][ny])
{
ans[nx][ny] = ans[x][y] + 1;
nc = c;
if (nx == n && ny == m) return;
heap.push((node) {ans[nx][ny],nx,ny,nc});
}
}
else
{
//否则不需要更改
if (ans[x][y] < ans[nx][ny])
{
ans[nx][ny] = ans[x][y];
if (nx == n && ny == m) return;
heap.push((node) {ans[nx][ny],nx,ny,Map[nx][ny]});
}
}
}
else// 左下/右上
{
if (c == 92) continue;
if (c != Map[nx][ny])//如果两个不同的话
{
//若要保证联通则必须更改
if (ans[x][y] + 1 < ans[nx][ny])
{
ans[nx][ny] = ans[x][y] + 1;
nc = c;
if (nx == n && ny == m) return;
heap.push((node) {ans[nx][ny],nx,ny,nc});
}
}
else
{
//否则不需要更改
if (ans[x][y] < ans[nx][ny])
{
ans[nx][ny] = ans[x][y];
if (nx == n && ny == m) return;
heap.push((node) {ans[nx][ny],nx,ny,Map[nx][ny]});
}
}
}
}
}
}
int main()
{
start.x = 1,start.y = 1,start.c = 92;
read(t);
while (t--)
{
read(n),read(m);
prework();
for (rg int i = 1;i <= n;++i) scanf("%s",Map[i] + 1);
if (Map[1][1] == '/') ++ans[1][1],Map[1][1] = 92;//ASCII
start.w = ans[1][1];
if ((n & 1) && !(m & 1))
{
puts("NO SOLUTION");
continue;
}
if (!(n & 1) && (m & 1))
{
puts("NO SOLUTION");
continue;
}
boy_friend_search();
print(ans[n][m]),__endl;
}
return 0;
}