题目描述
边权都相同的时候，每个点只会入队一次；
但边权不同时，每个点可能入队多次，需要st判重数组
这题是djk，和正常bfs思路不同，st数组意义不同
djk出队时，拿到元素了，判断st，若为0则设置为1
其他bfs则是在入队时就把st设为1
djk中 if(st==1) continue 的含义为，可能最开始时给了这个点一个dist，他已经入队了，但是因为这个dist不是最优的，这个点最初入队时一直在队伍后面，等到他有更优解的时候，已经提前出队并且st设置为1了，那第一次入队的这个点时的dist，就可以不用问了。直接continue
双端队列的思想：把边权为0的放前面，边权为1的放后面，可以使边权为1的后被遍历到
#include <iostream>
#include <cstring>
#include <deque>
#define x first
#define y second
using namespace std;
const int N=510;
int T,n,m;
char g[N][N];
int dist[N][N];
int st[N][N];
typedef pair<int,int> pii;
int bfs()
{
deque<pii> q;
memset(st,0,sizeof st);
memset(dist,0x3f,sizeof dist);
char cs[5]="\\/\\/";
int dx[4]={-1,-1,1,1}, dy[4]={-1,1,1,-1};
int ix[4]={-1,-1,0,0},iy[4]={-1,0,0,-1};
dist[0][0]=0;
q.push_back({0,0});
while(q.size())
{
auto t=q.front();
q.pop_front();
int x=t.x,y=t.y;
if(x==n && y==m) return dist[x][y];
if(st[x][y]) continue;
st[x][y]=1;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0||a>n||b<0||b>m) continue;
int ga=x+ix[i],gb=y+iy[i];
int w=(g[ga][gb]!=cs[i]);
int d=dist[x][y] +w;
if(d<=dist[a][b])
{
dist[a][b]=d;
if(!w) q.push_front({a,b});
else q.push_back({a,b});
}
}
}
return -1;
}
int main()
{
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>g[i][j];
}
}
if(n+m&1) cout<<"NO SOLUTION"<<endl;
else
cout<<bfs()<<endl;
}
}
二刷注意djk的实现思路，先判断距离d是否小于当前dist[a][b]小于再更新，再入队，且判断st要在出队时判断
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
const int N=510;
typedef pair<int,int> pii;
int dist[N][N];
char g[N][N];
int st[N][N];
int n,m,T;
char cs[5]="\\/\\/";
int dx[]={-1,-1,1,1};
int dy[]={-1,1,1,-1};
int drx[]={-1,-1,0,0};
int dry[]={-1,0,0,-1};
int bfs()
{
//(x==n&&y==m) return 0;
memset(st,0,sizeof st);
memset(dist,0x3f,sizeof dist);
deque<pii> q;
dist[0][0]=0;
//
q.push_back({0,0});
while(q.size())
{
auto t=q.front();
q.pop_front();
int tx=t.first;
int ty=t.second;
if(tx==n && ty==m) return dist[tx][ty];
if(st[tx][ty]) continue;
st[tx][ty]=1;
for(int i=0;i<4;i++)
{
int a=tx+dx[i];
int b=ty+dy[i];
if(a<0||a>n||b<0||b>m) continue;
int ga=tx+drx[i];
int gb=ty+dry[i];
int w=(g[ga][gb]!=cs[i]);
//djk算法更新距离,只有在当前距离小于之前距离的时候，才会push
int d=dist[tx][ty]+w;
if(d<dist[a][b])
{
dist[a][b]=d;
if(w==0)
{
q.push_front({a,b});
}
else
{
q.push_back({a,b});
}
}
}
}
return -1;
}
int main()
{
cin>>T;
while(T--)
{
cin>>n>>m;
//deque<pii> q;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>g[i][j];
}
}
if(m+n & 1) cout<<"NO SOLUTION"<<endl;
else
{
//bfs(0,0);
cout<<bfs()<<endl;
}
}
}
三刷，要注意x是行，y是列,一定不要搞反！！
在做双端队列的djk的时候
仔细想想djk的过程：
1. 判断st数组和更改st数组只在while循环里做（判断为0后更新）。第一个点设置dist之后，不设置st，st在while里设置
2. 在判断邻点时，不要判断st，因为每次做一个点的时候，他的邻点可能会反复更新，直到这个邻点进入队列开始遍历他时，才把st设置成1
3. 只有在d<dist[a][b]时才做push操作，边权为0插入队头，否则插入队尾
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
int T,n,m;
const int N=510;
int st[N][N];
char w[N][N];
int dist[N][N];
char road[]={'\\','/','\\','/'};
typedef pair<int,int> pii;
int dx_point[]={-1,-1,1,1};
int dy_point[]={-1,1,1,-1};
int dx_blank[]={-1,-1,0,0};
int dy_blank[]={-1,0,0,-1};
int bfs()
{
memset(dist,0x3f,sizeof dist);
memset(st,0,sizeof st);
deque<pii> q;
dist[1][1]=0;
q.push_back({1,1});
while(q.size())
{
auto t=q.front();
q.pop_front();
int x=t.first;
int y=t.second;
if(x==n+1 && y==m+1) return dist[x][y];
if(st[x][y]) continue;
st[x][y]=1;
for(int k=0;k<4;k++)
{
int a=x+dx_point[k];
int b=y+dy_point[k];
int ga=x+dx_blank[k];
int gb=y+dy_blank[k];
if(a<1 || a>n+1 || b<1 || b>m+1) continue;
int ww=(w[ga][gb]!=road[k]);
int d=dist[x][y] +ww;
if(d<dist[a][b])
{
dist[a][b]=d;
if(!ww) q.push_front({a,b});
else q.push_back({a,b});
}
}
}
return -1;
}
int main()
{
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>w[i][j];
}
}
if(n+m&1)
{
cout<<"NO SOLUTION"<<endl;
continue;
}
else
cout<<bfs()<<endl;
}
return 0;
}
2023/12/1
关键思路：
把问题看成一个无向图的最短路问题，只有两类边：
- 边权为0
- 边权为1(需要旋转)
求解从起点走到终点的最短路径
思路是关键，要能把这题抽象成01边权的最短路问题
详细代码解释：
- dx_blank：代表从当前点，按第i条road走，会经过的格子的序号
- 如果终点是 奇数，则不可能达到
总结一下djk
djk每次循环只能确定一个点是否已经是最短路径，st数组存的就是该点是否已经被确定过。
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
int T,n,m;
const int N=510;
int st[N][N];
char g[N][N];
int dist[N][N];
char road[]={'\\','/','\\','/'};
typedef pair<int,int> pii;
int dx_point[]={-1,-1,1,1};
int dy_point[]={-1,1,1,-1};
// 根据点的坐标，去找格子的坐标，去索引格子中存的字符
int dx_blank[]={-1,-1,0,0};
int dy_blank[]={-1,0,0,-1};
int main()
{
cin>>T;
while(T--)
{
memset(st, 0, sizeof(st));
memset(dist, 0x3f, sizeof(dist));
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
}
}
// 如果终点是 奇数，则不可能达到
if((n+1 + m+1)%2)
{
cout<<"NO SOLUTION"<<endl;
continue;
}
// 起点为(1,1), 终点为(n+1, m+1)
dist[1][1] = 0;
deque<pii> q;
q.push_front({1, 1});
while(q.size())
{
auto t = q.front();
q.pop_front();
int x=t.first;
int y=t.second;
// djk的做法，一个点出队时，说明它已经更新为最短路径
// 将其st设置为1, 并判断它的st是否已经为1
if(st[x][y]) continue;
st[x][y] = 1;
for(int i=0;i<4;i++)
{
// a,b为走到新点的坐标
int a=x+dx_point[i];
int b=y+dy_point[i];
// ra, rb为经过的格子的坐标
int ra=x+dx_blank[i];
int rb=y+dy_blank[i];
if(!(a>=1 && b>=1 && a<=n+1 && b<=m+1 && ra>=1 && rb>=1 && ra<=n && rb<=m))
{
continue;
}
// 如果第(ra, rb)中存的路径和第i条路径不同，则该条路的权值为1
int weight = 0;
if(g[ra][rb] != road[i])
{
weight = 1;
}
// 因为权值只有2种，因此使用双端队列，来模拟最小堆的djk
// 权值为0的放在前面，提前遍历到；权值为1的放在后面，最后遍历到
if(dist[a][b] > dist[x][y] + weight)
{
dist[a][b] = dist[x][y] + weight;
if(weight == 0)
{
q.push_front({a, b});
}
else if(weight == 1)
{
q.push_back({a, b});
}
}
}
}
cout<<dist[n+1][m+1]<<endl;
}
return 0;
}
三刷，哈哈哈，请问这一句 int w=(g[ga][gb]!=cs[i])；判断权值为0是什么意思
意思就是可以不用改变方向，直接通过（按照题目意思，如果需要改变管道的方向，则权值是1，那如果不需要改变就是0啦
明白