<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
此题解是对原帖中2.5.1节的翻新
前置知识
矩阵按行/列优先存储:
已知某一$r$行$c$列的矩阵$mat$,行号和列号都从0开始编号,从$addr_0$地址开始存储
则对于第$x$行$y$列的元素$mat[x][y]$:
按行优先存储,该元素的地址为$addr_0 + (x \* c + y) \* sizeof(ElemType)$;
按列优先存储,该元素的地址为$addr_0 + (y \* r + x) \* sizeof(ElemType)$;
其中$ElemType$指的是$mat$中存储元素的类型
算法1
Dijkstra (优先队列辅助版)
由图可知,原有的电路板无法按照黑色加粗的线从左上角直通右下角,那么把其中一格按照红色线改一改,使得这一格内的新路线和原路线垂直,就可以通到右下角
由此我们可以将网格中的每一个顶点看成无向图中的节点,每个顶点和它所处单元格对角处的顶点之间都有一条双向边,如果这条边穿过对应单元格的方向和原路线相同,那么这条边的权值为0,如果穿过单元格的方向和原路线垂直,那么这条边的权值为1,问题便转化为单源最短路问题。
考虑到无负权边的情况下spfa不占优,故采用优先队列辅助的Dijkstra来求解
单元格总数可达25w,每个单元格需要连接4条有向边,不用优先队列辅助的话会TLE
时间复杂度 $O(nlogn)$
其中$n = r \* c$,指的是单元格的总数
C++ 代码
#include <iostream>
#include <string.h>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 251010, M = 1004010;
//利用矩阵的行优先存储方式,可以将二维的坐标转换为一维,链式前向星可以用了
int fin[M], val[M], last[N], nxt[M], vis[N], dist[N];
//第一个数代表距离,第二个数代表位置
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> hp;
//有多组数据,把按行优先方式转换后的目标位置des,当前考虑的位置now,以及每一行输入的字符串row全部提到全局区
int tot = 0,now = 0,des = 0;
string row;
void connect(int s, int e, int v)
{
tot++;
fin[tot] = e;
val[tot] = v;
nxt[tot] = last[s];
last[s] = tot;
}
int main()
{
int t; cin >> t;
while (t--)
{
tot = 0;
memset(vis, 0, sizeof(vis));
memset(dist, 0x3f, sizeof(dist));
memset(last, 0, sizeof(last));
dist[0] = 0;
int r, c; cin >> r >> c;
//一共r+1行,c+1列
des = r * (c + 1) + c;
for (int i = 0; i < r; i++)
{
cin >> row;
for (int j = 0; j < c; j++)
{
now = (c + 1) * i + j;
if (row[j] == '/')//撇向,路线连通右上角与左下角
{
//按行优先存储,(i,j)的地址为now
//则(i,j+1)为now+1,(i+1,j)为now+c+1,(i+1,j+1)为now+c+2
connect(now, now + c + 2, 1);
connect(now + c + 2, now, 1);
connect(now + 1, now + c + 1, 0);
connect(now + c + 1, now + 1, 0);
}
else//捺向,路线连通右下角与左上角
{
connect(now, now + c + 2, 0);
connect(now + c + 2, now, 0);
connect(now + 1, now + c + 1, 1);
connect(now + c + 1, now + 1, 1);
}
}
}
//下面就是优先队列辅助的Dijkstra
hp.push({ 0,0 });
while (!hp.empty())
{
pair<int, int> cur = hp.top();
hp.pop();
int curPos = cur.second, curDist = cur.first;
if (vis[curPos] == 1) continue;
vis[curPos] = 1;
for (int i = last[curPos]; i != 0; i = nxt[i])
{
int nextPos = fin[i];
if (dist[nextPos] > dist[curPos] + val[i])
{
dist[nextPos] = dist[curPos] + val[i];
hp.push({ dist[nextPos],nextPos });
}
}
}
if (dist[des] > 1e8) cout << "NO SOLUTION" << endl;
else cout << dist[des] << endl;
}
return 0;
}
算法2
双端队列广搜
Dijkstra算法在此处复杂度还是略高了,实际上边权也就0,1两个值,用双端队列deque存放顶点位置,最近经过边权为0的从队头入队,边权为1的从队尾入队,手动维护单调性,可以将时复降低到$O(n)$
先用一张图解释一下代码中的顶点偏移和单元格偏移:
(行号列号标反了,横向对应行号,纵向对应列号,原理相同)
另外有一个预先剪枝的地方,就是顶点的行列号相加为奇数的点一定不可达,因此$r+c$如果为奇数就可以直接输出无解
时间复杂度 $O(n)$
n的定义和Dijkstra中相同
C++ 代码
#include <iostream>
#include <deque>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 505;
//同样按行优先存储
inline int key(int x,int y)
{
return x * N + y;
}
char wires[N][N];
int dist[N][N],vis[N][N];
//分别表示顶点偏移和单元格偏移
int point_dx[4] = {-1,-1,1,1},
point_dy[4] = {-1,1,1,-1},
block_dx[4] = {-1,-1,0,0},
block_dy[4] = {-1,0,0,-1};
char dir[4] = {'\\','/','\\','/'};
deque<int> dq;
int leastRotates(int r,int c)
{
//用双端队列代替优先队列
dq.clear();
dq.push_back(0);//(0,0)行优先之后的索引值还是0
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[0][0] = 0;
while(!dq.empty())
{
//一样是采用行优先存储
int cur = dq.front();
dq.pop_front();
int ox = cur / N,oy = cur % N;
if(ox == r && oy == c) return dist[ox][oy];
if(vis[ox][oy] == 1) continue;
vis[ox][oy] = 1;
for(int i = 0;i < 4;i++)
{
int nx = ox + point_dx[i],ny = oy + point_dy[i];//即将到达的顶点
if(nx < 0 || ny < 0 || nx > r || ny > c) continue;
int wx = ox + block_dx[i],wy = oy + block_dy[i];//穿过的单元格
int val = wires[wx][wy] != dir[i];//bool类型的true/false就是整数型的1/0
if(dist[nx][ny] >= dist[ox][oy] + val)
{
dist[nx][ny] = dist[ox][oy] + val;
//手动维护单调性,跟优先队列push一样
if(val == 0) dq.push_front(key(nx,ny));
else dq.push_back(key(nx,ny));
}
}
}
return -1;
}
int main()
{
int t;cin >> t;
while(t--)
{
int r,c;cin>>r>>c;
for(int i = 0;i < r;i++) cin>>wires[i];
if((r + c) % 2 == 1) cout << "NO SOLUTION" << endl;
else cout << leastRotates(r,c) << endl;
}
return 0;
}