求助,这题样例未过30分,求各位巨佬帮我看下
查看原帖
求助,这题样例未过30分,求各位巨佬帮我看下
687620
Salazar_byy楼主2023/10/1 09:19
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x;
	int y;
	int time;
	int direction;
};
int n,m;
int vis[55][55][2];
int grid[55][55];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
queue <node> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>grid[i][j];
			if(grid[i][j]==1){
				grid[i-1][j]=1;
				grid[i][j-1]=1;
				grid[i-1][j-1]=1;
			}
		}
	}
	int bx,by,ex,ey,bd;
	char di;
	cin>>bx>>by>>ex>>ey;
	cin>>di;
	if(di=='E') bd=0;
	else if(di=='S') bd=1;
	else if(di=='W') bd==2;
	else bd==3;
    node tmp;
    tmp.x=bx,tmp.y=by,tmp.time=0,tmp.direction=bd;
    q.push(tmp);
    vis[tmp.x][tmp.y][tmp.direction]=1;
    while(!q.empty()){
    	node cur = q.front();
    	q.pop();
    	int xx=cur.x,yy=cur.y;
    	if(xx==ex&&yy==ey) {
    		cout<<cur.time<<endl;
    		return 0;
		}
    	for(int i=1;i<=3;i++){
    		int nx=xx+dx[cur.direction],ny=yy+dy[cur.direction];
    		if(nx>1 && nx<n && ny>1 && ny<m && !grid[nx][ny] && !vis[nx][ny][cur.direction]){
    			vis[nx][ny][cur.direction]=1;
    			q.push(node{nx,ny,cur.time+1,cur.direction});
			}
		}
		node nnew=cur;
		nnew.time=cur.time+1;
		nnew.direction=cur.direction-1;
		if(nnew.direction==-1) nnew.direction=3;
		if(!vis[nnew.x][nnew.y][nnew.direction]){
	        vis[nnew.x][nnew.y][nnew.direction]=1;	
			q.push(nnew);
		}
		nnew.direction=cur.direction+1;
		if(nnew.direction==4) nnew.direction=0;
		if(!vis[nnew.x][nnew.y][nnew.direction]){
	        vis[nnew.x][nnew.y][nnew.direction]=1;	
			q.push(nnew);
		}
	}
	cout<<-1;
	return 0;
}
2023/10/1 09:19
加载中...