前程无忧做网站多少钱,学做预算网站,西安网站建设服务商十强,济南制作网站的公司哪家好达达是来自异世界的魔女#xff0c;她在漫无目的地四处漂流的时候#xff0c;遇到了善良的少女翰翰#xff0c;从而被收留在地球上。
翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障#xff0c;导致无法启动。电路板的整体结构是一个 R 行 C 列的网格#…达达是来自异世界的魔女她在漫无目的地四处漂流的时候遇到了善良的少女翰翰从而被收留在地球上。
翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障导致无法启动。电路板的整体结构是一个 R 行 C 列的网格R,C≤500如下图所示。 每个格点都是电线的接点每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变电路板可能处于断路的状态。她准备通过计算旋转最少数量的元件使电源与发动装置通过若干条短缆相连。不过电路的规模实在是太大了达达并不擅长编程希望你能够帮她解决这个问题。
注意只能走斜向的线段水平和竖直线段不能走。
输入格式 输入文件包含多组测试数据。 第一行包含一个整数 T表示测试数据的数目。 对于每组测试数据第一行包含正整数 R 和 C表示电路板的行数和列数。 之后 R 行每行 C 个字符字符是/和\中的一个表示标准件的方向。
输出格式 对于每组测试数据在单独的一行输出一个正整数表示所需的最小旋转次数。 如果无论怎样都不能使得电源和发动机之间连通输出 NO SOLUTION。
数据范围 1≤R,C≤500,1≤T≤5
输入样例
1 3 5 \\/\\ \\/// /\\\\ 输出样例 1
样例解释 样例的输入对应于题目描述中的情况。 只需要按照下面的方式旋转标准件就可以使得电源和发动机之间连通。 解析
从(0,0) 走到 (n,m)的过程中能走的边权为0需要旋转的边权为1。
旋转最少数量的元件也就是从(0,0) 走到 (n,m)的最短距离。
这道题用的是双端队列BFS也可以说是特殊的 Dijkstra.
注意对于每个点它要走的下一个点只能是坐标和为偶数的点也就是左上、右上、右下、左下。
#include bits/stdc.h
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pairint,int PII;
const int N2e610;
deque PII q;
char g[510][510];
bool vis[510][510];
int d[510][510];
int n,m;
int dx[4]{-1,-1,1,1}; //该点下步的点(起点是(0,0),之后走的点就是坐标和为偶数的点)即左上、右上、右下、左下
int dy[4]{-1,1,1,-1};int ix[4]{-1,-1,0,0}; //该点下步的点的状态
int iy[4]{-1,0,0,-1};char c[5]\\/\\/; //该点下步的点的理想状态 (若权值为0的状态)
void bfs()
{memset(vis,0,sizeof vis);memset(d,0x3f,sizeof d);q.push_back({0,0});d[0][0]0;while (q.size()){int xq.front().first;int yq.front().second;q.pop_front();if (vis[x][y]) continue;vis[x][y]1;for (int i0;i4;i){int axdx[i],bydy[i];if (a0anb0bm){int gaxix[i],gbyiy[i];int w(g[ga][gb]!c[i]);if (d[x][y]wd[a][b]){d[a][b]d[x][y]w;if (w) q.push_back({a,b});else q.push_front({a,b});}}}}
}
signed main()
{ios;int t;cint;while (t--){cinnm;for (int i0;in;i)for (int j0;jm;j)cing[i][j];if ((nm)%2!0) coutNO SOLUTION\n; //(nm)如果是奇数就走不到该点即无解else {bfs();coutd[n][m]endl;}}return 0;
}
