https://loj.ac/problem/2632
题目描述
给出(n)行(m)列的斜线,要求从((0,0))走到((n,m)),只能往四个斜方向走,若斜线方向与走的方向相同,花费为(0),否则花费为(1).
思路
比较经典的(bfs)题,可以看做是(0,1)最短路,用双端队列解决。用双端队列是为了维护队列中的单调性,即队列中元素的(step)一定时从队首到队尾单调递增的(并不严格递增)。不过这道题有一些细节需要注意。
首先你要处理好路和点的关系,明确往哪里走需要查看的是那一条斜线。
其次一个重要的点括号中也有提到,由于(step)并不是严格单增,所以我们并不能用(vis)数组储存是否访问过,因为例如我们现在在((2,2)),到目前花费为(0),能以(1)的代价走到((3,1)),用(vis)数组记录后,从((2,0))能以总代价(1)走到((3,1)),但由于已经访问过会忽略。所以我们可以用一个(cost)数组储存到((x,y))的最小花费,比较是否比最小花费小即可。
代码
#include<bits/stdc++.h>
using namespace std;
struct aa
{
int x,y,step;
aa(int x=0,int y=0,int step=0):x(x),y(y),step(step) {}
};
int dx[4]={1,1,-1,-1},dy[4]={1,-1,1,-1};
int px[4]={0,0,1,1},py[4]={0,1,0,1};
char mp[550][550];
bool check(int x,int y,int t)
{
if(mp[x][y]=='/')
{
if(t==0||t==3)return 1;
else return 0;
}
else
{
if(t==0||t==3)return 0;
else return 1;
}
}
int cost[550][550];
int n,m;
bool valid(int x,int y){return x>=0&&y>=0&&x<=n&&y<=m;}
void bfs(int sx,int sy)
{
memset(cost,0x3f,sizeof(cost));
deque<aa>q;
q.push_front(aa(sx,sy,0));
cost[sx][sy]=0;
while(!q.empty())
{
aa u=q.front();q.pop_front();
if(u.x==n&&u.y==m)
{
printf("%d",u.step);
return ;
}
for(int i=0;i<4;i++)
{
int nx=u.x+dx[i];
int ny=u.y+dy[i];
if(valid(nx,ny))
{
bool f=check(nx+px[i],ny+py[i],i);//用p数组实现斜线和点的转移
if(cost[nx][ny]<=cost[u.x][u.y]+f)continue ;//比较到这个点的花费,有等号
cost[nx][ny]=cost[u.x][u.y]+f;
if(f)q.push_back(aa(nx,ny,u.step+1));//双端队列放队首、队尾
else q.push_front(aa(nx,ny,u.step));
}
}
}
printf("NO SOLUTION");
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf(" %s",mp[i]+1);
bfs(0,0);
}