求助TLE&MLE,貌似和一些题解的BFS差不多啊。
查看原帖
求助TLE&MLE,貌似和一些题解的BFS差不多啊。
242490
lyc呐楼主2020/8/13 10:35
#include<bits/stdc++.h>
using namespace std;
struct node{
	short int x;
	short int y;
	int step=0;
};
int f[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	char map[305][305];
	short int judge[305][305]={{0}};
	node p;
	string s;
	for(int i=0;i<n;i++)	//输入 
	{
		cin>>s;
		for(int j=0;j<m;j++)
		{
			map[i][j]=s[j];
			if(map[i][j]=='@')
				p.x=i,p.y=j,p.step=0;			
		}
	}
	queue <node> Q;
	Q.push(p);
	while(!Q.empty())				//BFS
	{
		p=Q.front();
		if(map[p.x][p.y]=='=')		//到达终点 
		{
			printf("%d",p.step);	
			return 0; 
		}
		if(map[p.x][p.y]<'A'||map[p.x][p.y]>'Z'||judge[p.x][p.y]>1)
			map[p.x][p.y]='#';			//走过标记 
		else
			judge[p.x][p.y]++;
		Q.pop();
		node temp;
		for(int i=0;i<4;i++)		//四个方向 
		{
			if(p.x+f[i][0]<n&&p.x+f[i][0]>=0&&p.y+f[i][1]<m&&p.y+f[i][1]>=0)	//没有越界 
			{
				if(map[p.x+f[i][0]][p.y+f[i][1]]!='#')		//可以走 
				{
					if(map[p.x+f[i][0]][p.y+f[i][1]]>='A'&&map[p.x+f[i][0]][p.y+f[i][1]]<='Z')	//传送门特判 
					{
						bool flag=false,ifHave=false;
						for(int k=0;k<n;k++)
						{
							for(int j=0;j<m;j++)
							{
								if(map[k][j]==map[p.x+f[i][0]][p.y+f[i][1]]&&(k!=p.x+f[i][0]||j!=p.y+f[i][1]))
								{
									temp.x=k,temp.y=j,ifHave=flag=true;
									break;									
								}
								if(flag)
									break;
							}							
						}
						if(!ifHave)			//如果没有匹配的传送门 
						{
							temp.x=p.x+f[i][0];
							temp.y=p.y+f[i][1];								
						}
					}
					else		//不是传送门直接走 
					{
						temp.x=p.x+f[i][0];
						temp.y=p.y+f[i][1];							
					}										
					temp.step=p.step+1;
					Q.push(temp);
				}	
			}			
		}
	}
}
2020/8/13 10:35
加载中...