#include "cstdio"
#include "vector"
#include "cstring"
#include "queue"
 
using namespace std;
char g[43][43];
int n,m;
int s_x;
int s_y;
int t_x;
int t_y;
//left
int move_leftx[4][4] = {{0,-1,0,+1},{-1,0,+1,0},{0,+1,0,-1},{+1,0,-1,0}};
int move_lefty[4][4] = {{-1,0,+1,0},{0,+1,0,-1},{+1,0,-1,0},{0,-1,0,+1}};

int move_leftd[4][4] = {{3,0,1,2},{0,1,2,3},{1,2,3,0},{2,3,0,1}};
int move_rightd[4][4] = {{1,0,3,2},{2,1,0,3},{3,2,1,0},{0,3,2,1}};

//right
int move_rightx[4][4] = {{0,-1,0,+1},{+1,0,-1,0},{0,+1,0,-1},{-1,0,+1,0}};
int move_righty[4][4] = {{+1,0,-1,0},{0,+1,0,-1},{-1,0,+1,0},{0,-1,0,+1}};
//bfs
int move_bfs[][2] = {{-1,0},{+1,0},{0,-1},{0,+1}}; 
bool visited[43][43];
int dist[43][43];
bool access(int x,int y)
{
	if(x >= 0 && x < m && y >= 0 && y < n && g[x][y] != '#')
	{
		return true;
	}
	return false;
}
bool access_bfs(int x,int y)
{
	if(x >= 0 && x < m && y >= 0 && y < n && g[x][y] != '#' && !visited[x][y])
	{
		return true;
	}
	return false;
}
int dfs_left(int rx,int ry,int d,int num)
{
	if(rx == t_x && ry == t_y)
	{
		return num+1;
	}
	for(int i = 0 ; i < 4 ; i++)
	{
		int nx = rx + move_leftx[d][i];
		int ny = ry + move_lefty[d][i];
		if(access(nx,ny))
		{
			int nd ;
			nd = move_leftd[d][i];
			return dfs_left(nx,ny,nd,num+1);
			
		}
	}

}

int dfs_right(int rx,int ry,int d,int num)
{
	if(rx == t_x && ry == t_y)
	{
		return num+1;
	}
	for(int i = 0 ; i < 4 ; i++)
	{
		int nx = rx + move_rightx[d][i];
		int ny = ry + move_righty[d][i];
		if(access(nx,ny))
		{
			int nd ;
			nd = move_rightd[d][i];
			return dfs_right(nx,ny,nd,num+1);
			

		}
	}

}
int bfs()
{
	memset(visited,false,sizeof(visited));
	memset(dist,0,sizeof(dist));
	queue<int> qx;
	queue<int> qy;
	qx.push(s_x);
	qy.push(s_y);
	visited[s_x][s_y] = true;
	dist[s_x][s_y] = 1;
	while(!qx.empty() && !qy.empty())
	{
		int x = qx.front();
		int y = qy.front();
		qx.pop();
		qy.pop();
		if(x == t_x && y == t_y)
		{
			return dist[x][y];
		}
		for(int i = 0 ;i < 4 ; i++)
		{
			int nx = x + move_bfs[i][0];
			int ny = y + move_bfs[i][1];
			if(access_bfs(nx,ny))
			{
				dist[nx][ny] = dist[x][y]+1;
				qx.push(nx);
				qy.push(ny);
			}
		}
	}
}
int initD()
{
	if(s_x == m-1)
		return 0;
	if(s_x == 0)
		return 2;
	if(s_y == 0)
		return 1;
	if(s_y == n-1)
		return 3;

}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		
		scanf("%d %d",&n,&m);

		for(int i = 0 ;i < m ; i++)
		{
			char s[60];
			scanf("%s",s);
			for(int j = 0 ; j < n ; j++)
			{
				g[i][j] = s[j];
				if(g[i][j] == 'S')
				{
					s_x = i;
					s_y = j;
				}
				if(g[i][j] == 'E')
				{
					t_x = i;
					t_y = j;
				}
			}
		}
		int d = initD();
		int r1 = dfs_left(s_x,s_y,d,0);
		int r2 = dfs_right(s_x,s_y,d,0);
		int r3 = bfs();
		printf("%d %d %d\n",r1,r2,r3);

	}
	//while(1)
	//{}
	return 0;
}

• Re:一直是Memory Limit Exceeded，求大神帮忙看看呗？bfs+dfs (11) zhangdanfeng 2017-12-26 15:08:47
• Re:一直是Memory Limit Exceeded，求大神帮忙看看呗？bfs+dfs (28) lynne5918 2020-08-16 16:40:28
• Re:一直是Memory Limit Exceeded，求大神帮忙看看呗？bfs+dfs (3298) pankaiwen121 2024-05-08 21:30:58