1 条题解

  • 0
    @ 2025-5-25 18:12:21
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <queue>
    
    #define MAXN 41
    
    using namespace std;
    
    char maze[MAXN][MAXN];
    int T;
    int w, h;
    int sx, sy, ex, ey;
    int dirx[] = { 0, -1, 0, 1 };
    int diry[] = { -1, 0, 1, 0 };
    //L,U,R,D
    
    struct Location{
    	int x, y, step;
    	Location(){}
    	Location(int xx, int yy, int ss) :x(xx), y(yy), step(ss){}
    };
    
    void DFS(int x, int y, int& step, int face, int rule)
    {
    	for (int i = 0; i < 4; i++)
    	{
    		int index, xx, yy;
    		if (rule == 1)//left
    			index = (face + 3 + i) % 4;
    		else//right
    			index = (face + 5 - i) % 4;
    		
    		xx = x + dirx[index];
    		yy = y + diry[index];
    		
    		if (xx == ex && yy == ey)
    		{
    			step++;
    			break;
    		}
    		else if (xx < 0 || xx >= h || yy < 0 || yy >= w)
    			continue;
    		else if (maze[xx][yy] == '#')
    			continue;
    		else
    		{
    			DFS(xx, yy, ++step, index, rule);
    			break;
    		}
    	}
    }
    
    int BFS()
    {
    	bool vis[MAXN][MAXN];
    	memset(vis, 0, sizeof(vis));
    	vis[sx][sy] = true;
    	
    	queue<Location> q;
    	q.push(Location(sx, sy, 1));
    	
    	while (!q.empty())
    	{
    		Location p = q.front();
    		q.pop();
    		if (p.x == ex && p.y == ey)
    			return p.step;
    		for (int i = 0; i < 4; i++)
    		{
    			Location tmp(p.x + dirx[i], p.y + diry[i], p.step + 1);
    			if (tmp.x < 0 || tmp.x >= h || tmp.y < 0 || tmp.y >= w)
    				continue;
    			if (maze[tmp.x][tmp.y] != '#'&&!vis[tmp.x][tmp.y])
    			{
    				q.push(tmp);
    				vis[tmp.x][tmp.y] = true;
    			}
    		}
    	}
    }
    
    int main(int argc, char** argv)
    {
    	scanf("%d", &T);
    	while (T--)
    	{
    		scanf("%d%d", &w, &h);
    		for (int i = 0; i < h; i++)
    		{
    			scanf("%s", maze[i]);
    			for (int j = 0; j < w; j++)
    			{
    				//scanf(" %c", &maze[i][j]);
    				if (maze[i][j] == 'S')
    				{
    					sx = i;
    					sy = j;
    				}
    				else if (maze[i][j] == 'E')
    				{
    					ex = i;
    					ey = j;
    				}
    			}
    		}
    		int face;
    		if (sx == 0)
    			face = 3;
    		else if (sx == h - 1)
    			face = 1;
    		else if (sy == 0)
    			face = 2;
    		else
    			face = 0;
    		int step = 1;
    		DFS(sx, sy, step, face, 1);
    		printf("%d ", step);
    		step = 1;
    		DFS(sx, sy, step, face, 0);
    		printf("%d ", step);
    		printf("%d\n", BFS());
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    2084
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    1
    已通过
    1
    上传者