首页 > 试题广场 > 对称飞行器
[编程题]对称飞行器
  • 热度指数:50 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小强在玩一个走迷宫的游戏,他操控的人物现在位于迷宫的起点,他的目标是尽快的到达终点。
每一次他可以选择花费一个时间单位向上或向下或向左或向右走一格,或是使用自己的对称飞行器花费一个时间单位瞬移到关于当前自己点中心对称的格子,且每一次移动的目的地不能存在障碍物。
具体来说,设当前迷宫有  行  列,如果当前小强操控的人物位于点 ,那么关于点  中心对称的格子 满足
需要注意的是,对称飞行器最多使用次。

输入描述:
第一行两个空格分隔的正整数  ,分别代表迷宫的行数和列数。
接下来  行 每行一个长度为  的字符串来描述这个迷宫。
其中
 代表通路。
 代表障碍。
 代表起点。
 代表终点。
保证只有一个  和 一个  。


输出描述:
仅一行一个整数表示从起点最小花费多少时间单位到达终点。
如果无法到达终点,输出 
示例1

输入

4 4
#S..
E#..
#...
....

输出

4

说明

一种可行的路径是用对称飞行器到达 \text (4,3) 再向上走一步,再向右走一步,然后使用一次对称飞行器到达终点。

BFS

from collections import deque

n, m = map(int, input().split())
migong = [input() for _ in range(n)]
S = (0, 0), 0
E = (0, 0)
for i, row in enumerate(migong, 1):
    for j, col in enumerate(row, 1):
        if col == "S":
            S = (i, j), 0
        if col == "E":
            E = (i, j)
q = deque([S])
direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
isvisited = set([S[0]])


def move(pos: tuple[tuple[int, int], int], dir: tuple[int, int]):
    (x, y), _ = pos
    dx, dy = dir
    return (x + dx, y + dy), _


def jmp(pos: tuple[tuple[int, int], int]):
    (x, y), _ = pos
    return (n + 1 - x, m + 1 - y), _ + 1


def check(pos: tuple[tuple[int, int], int]):
    (x, y), times = pos
    return (
        1 <= x <= m
        and 1 <= y <= n
        and migong[x - 1][y - 1] != "#"
        and times <= 5
        and (x, y) not in isvisited
    )


# print(migong, E, S)

cnt = 0
success = False
while q:
    l = len(q)
    for _ in range(l):
        t = q.pop()
        # print(t)
        if t[0] == E:
            print(cnt)
            success = True
            break
        for j in direction:
            tt = move(t, j)
            # print(tt)
            if check(tt):
                # print(tt)
                isvisited.add(tt[0])
                q.appendleft(tt)

        jmpt = jmp(t)
        # print(jmpt)
        if check(jmpt):
            q.appendleft(jmpt)
            isvisited.add(jmpt[0])
    cnt += 1
if not success:
    print(-1)
"""
4 4
#S..
E#..
#...
....
"""
发表于 2021-05-08 10:43:18 回复(0)
广搜,不过数组开3维。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node
{
    int x,y,t;
};
int n,m,sx,sy,ex,ey,v[505][505][6];
int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
char a[505][505];
queue<node>q;
void bfs(int x,int y)
{
    v[x][y][0]=1;
    int i,j,t,nx,ny;
    q.push({x,y,0});
    while(q.size())
    {
        x=q.front().x,y=q.front().y,t=q.front().t;
        q.pop();
        for(i=0; i<5; i++)
        {
            if(i==4)
            {
                if(t<5)
                    nx=n+1-x,ny=m+1-y,t++;
                else
                    continue;
            }
            else
                nx=x+dx[i],ny=y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&v[nx][ny][t]==0)
            {
                if(i==4)
                    v[nx][ny][t]=v[x][y][t-1]+1;
                else
                    v[nx][ny][t]=v[x][y][t]+1;
                if(nx==ex&&ny==ey)
                    return;
                q.push({nx,ny,t});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,ans=-1;
    cin>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='S')
                sx=i,sy=j;
            if(a[i][j]=='E')
                ex=i,ey=j;
        }
    bfs(sx,sy);
    for(i=0; i<6; i++)
        if(v[ex][ey][i])
            ans=v[ex][ey][i]-1;
    cout<<ans;
    return 0;
}


发表于 2021-05-02 18:54:50 回复(0)