F请各位看看

https://ac.nowcoder.com/acm/contest/86387/F
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;

#define ll long long
#define all(x) (x).begin(),(x).end()
const int N=1e3+10;

int n,m;
char dt[N][N];
int dx[]={0,-1,1,0};
int dy[]={-1,0,0,1};
int dis[N][N],vis[N][N][5];
struct ss{
	int x,y,s,no;
	bool operator<(const struct ss& a)const{
		return this->s>a.s;
	}
};
bool check(int x,int y){
	if(x>=1 && x<=n && y>=1 && y<=m) return true;
	return false;
}
void dijkstra(){
	memset(dis,0x3f,sizeof dis);
	priority_queue<ss> pq;
	dis[1][1]=0,pq.push({1,1,0,-1});
	while(!pq.empty()){
		auto t=pq.top(); pq.pop();
		int x=t.x,y=t.y;
        // -1表示上下左右都可以移动
		if(vis[x][y][(t.no+5)%5]) continue;
		vis[x][y][(t.no+5)%5]=1;
		
		for(int i=0;i<4;i++){
			if(i==t.no) continue;
			int xx=x+dx[i];
			int yy=y+dy[i];
			
			if(!check(xx,yy)) continue;
			if(dt[xx][yy]=='.'){
				if(dis[x][y]+1<dis[xx][yy]){
					dis[xx][yy]=dis[x][y]+1;
					pq.push({xx,yy,dis[xx][yy],t.no});
				}
			}
			else{
				if(t.no!=-1) continue;
				if(dis[x][y]+1<dis[xx][yy]){
					dis[xx][yy]=dis[x][y]+1;
					for(int j=0;j<4;j++)
						if(i!=j) pq.push({xx,yy,dis[xx][yy],j});
				}
			}
		}
	}
	cout<<(dis[n][m]==0x3f3f3f3f?-1:dis[n][m]);
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>dt[i][j];
	dijkstra();
	return 0;
}

全部评论

相关推荐

07-07 17:06
已编辑
深圳技术大学 golang
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务