萌新求助,修不动了
查看原帖
萌新求助,修不动了
171521
SCWLine楼主2021/11/11 14:09

修了半天终于不TLE了 (变成WA了

有没有大佬帮忙看一下有什么问题

#include<iostream>
#include<queue>
#include<map>
using namespace std;

int n,m;
int dbcx[]={0,1,0,1};
int dbcy[]={0,0,1,1};//用于bodycheck 
map<char,int> dx;
map<char,int> dy;//用于前进 
map<char,map<char,char> > turn;//用于转向 

map<int,map<int, map<char, bool> > >  vis;


int sx,sy,ex,ey;
char sd;
int f[51][51];


struct pt
{
   pt(int _x,int _y,int _s,char _d,int _w):x(_x),y(_y),sum(_s),dir(_d),walk(_w){};
   int x,y,sum,walk;//x坐标,y坐标,花费时间,在这个方向上走了多少步 
   char dir;//机器人方向 
};

void initmap()
{
   dx['E']=1;dy['E']=0;
   dx['W']=-1;dy['W']=0;
   dx['S']=0;dy['S']=1;
   dx['N']=0;dy['N']=-1;
   
   turn['E']['L']='N';turn['E']['R']='S';turn['E']['B']='W';
   turn['W']['L']='S';turn['W']['R']='N';turn['W']['B']='E';
   turn['S']['L']='E';turn['S']['R']='W';turn['S']['B']='N';
   turn['N']['L']='W';turn['N']['R']='E';turn['N']['B']='S';
}
//丧心病狂初始化 

bool bodycheck(int bcx,int bcy)
{
   for(int i=0;i<4;i++)
   {
   	int nx=bcx+dbcx[i],ny=bcy+dbcy[i];
   	if(nx<1||ny<1||nx>n||ny>m||f[nx][ny]==1)	return false;
   }
   return true;
}//检查x,y这个地方能不能放下一个机器人 




int main()
{
   
   cin>>n>>m;
   for(int i=1;i<=n;i++)
   	for(int j=1;j<=m;j++)
   		cin>>f[i][j];
   queue<pt> list;
   cin>>sx>>sy>>ex>>ey>>sd;
   
   
   initmap();
   list.push(pt(sx,sy,0,sd,0));
   while(!list.empty())
   {
   	pt pot=list.front();
   	list.pop();
   	vis[pot.x][pot.y][pot.dir]=true;
   	
   	if(pot.x==ex&&pot.y==ey)
   	{
   		cout<<pot.sum;
   		return 0;
   	}	//到点输出 
   	
   	int nx=pot.x+dx[pot.dir],ny=pot.y+dy[pot.dir];//向面对着的方向前进 
   	if(bodycheck(nx,ny)&&(!vis[nx][ny][pot.dir]))//可以走且没走过 
   	{
   		if(pot.walk==3)//已经向前走过了3步 
   		list.push(pt(nx,ny,pot.sum+1,pot.dir,0));
   		else if(pot.walk==0)//1步都没走过 
   		list.push(pt(nx,ny,pot.sum+1,pot.dir,pot.walk+1));
   		else//这个方向已经走过且还没走够三步 
   		list.push(pt(nx,ny,pot.sum,pot.dir,pot.walk+1));
   	}
   	
   		if(!vis[pot.x][pot.y][turn[pot.dir]['L']])//左转 
   		list.push(pt(pot.x,pot.y,pot.sum+1,turn[pot.dir]['L'],0));
   		if(!vis[pot.x][pot.y][turn[pot.dir]['R']])//右转 
   		list.push(pt(pot.x,pot.y,pot.sum+1,turn[pot.dir]['R'],0));
   		if(!vis[pot.x][pot.y][turn[pot.dir]['B']])//掉头 
   		list.push(pt(pot.x,pot.y,pot.sum+2,turn[pot.dir]['B'],0));
   
   }
   cout<<-1;
   return 0;
}
2021/11/11 14:09
加载中...