首页 > 试题广场 >

ACM中的AC题

[编程题]ACM中的AC题
  • 热度指数：430 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}众所周知，出题人没玩过《双人成行》，于是给出了如下经典二人协作版迷宫问题。孤岛被划分为 n \times m 个方格，按行从上到下、列从左到右编号为 (1,1) 至 (n,m)。地图上的地形分为三种：
\hspace{23pt}\bullet\,平地（`.`）——可以自由经过；
\hspace{23pt}\bullet\,陷阱（`#`）——踩上去立即死亡；
\hspace{23pt}\bullet\,传送门（`@`）——一旦进入便会立刻离开孤岛。

\hspace{15pt}你与来自平行时空的另一个"你"最初同时位于坐标 (x,y) 的同一块平地。两人每次必须同时行动，且朝相反方向各移动一步，即：
\hspace{23pt}\bullet\,如果你选择向上，则另一个你必须向下；
\hspace{23pt}\bullet\,如果你选择向左，则另一个你必须向右，依此类推。

\hspace{15pt}在任何时刻，若有人走出边界或踏入陷阱，游戏立即失败；若有人到达传送门，则他会立刻离开并不再返回，之后剩下的那个人可以单独自由移动（不再受"相反方向"限制）。

\hspace{15pt}请判断是否存在一条合法的移动序列，使得两个人都能成功离开孤岛；若存在，请输出最短所需步数，否则输出 -1。

输入描述:
\hspace{15pt}输入包含 n+1 行：
\hspace{23pt}\bullet\,第一行输入四个整数 n,m,x,y\left(1\leqq n,m\leqq 2\times10^{3};\ 1\leqq x\leqq n;\ 1\leqq y\leqq m\right)；
\hspace{23pt}\bullet\,接下来 n 行，第 i 行输入一个长度为 m 的字符串 s_i，仅由 `.`、`#`、`@` 组成，描述第 i 行的地形。
\hspace{15pt}保证起点 (x,y) 处为平地。


输出描述:
\hspace{15pt}若存在可行方案，输出最短移动步数；否则输出 -1。
示例1

输入

3 3 2 2
@.@
#..
@.@

输出

2

说明

你可以先往上后往左到达(1,1)传送门
另外一个时空的你会先下后右到达(3,3)传送门
示例2

输入

1 3 1 2
..@

输出

3
示例3

输入

3 1 2 1
#
.
@

输出

-1

说明

显然，谁都不想走到陷阱那 ...

备注:

算法知识视频讲解
添加回答
Python3
kv001头像 kv001
我这段代码在提交时,有一个输入死活不过,我调试了一下,我判断的是有解(print True),但官方给的是无解(-1).   
import sys
from collections import deque

def solve_dual_maze_packed(tokens):
    ptr = 0
    n, m, sx, sy = map(int, tokens[ptr:ptr+4])
    ptr += 4
    grid = [tokens[ptr+i] for i in range(n)]

    dirs = [(-1,0),(1,0),(0,-1),(0,1)]  # 上下左右    
    sx0, sy0 = sx-1, sy-1

    #先看看有没有解
    if grid[sx0][sy0] == '#':
        print(-1)
   
    visited = [[False]*m for _ in range(n)]
    visited[sx0][sy0] = True
    q = deque()
    q.append((sx0, sy0))
    has_ans = False
    while q:
        x, y = q.popleft()
       
        # A 到出口了
        if grid[x][y] == '@':
            has_ans = True
            break
       
        for dx, dy in dirs:
            nx, ny = x+dx, y+dy
            mx, my = x-dx, y-dy  # 镜像 B 的移动
           
            if 0 <= nx < n and 0 <= ny < m and 0 <= mx < n and 0 <= my < m:
                if grid[nx][ny] != '#' and grid[mx][my] != '#' and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))
   
    if(n==1999 and m==1999 and sx==999 and sy==999 and grid[0].startswith('@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@')):
        print(has_ans)
        return
    if not has_ans:
        print(-1)
        return
   

    # BFS 队列
    start_key = (sx0, sy0, sx0, sy0)
    q = deque()
    q.append((sx0, sy0, sx0, sy0, 0))
    visited = set([start_key])

    while q:
        ax, ay, bx, by, step = q.popleft()

        # 判断是否有人已经到出口
        a_exit = (ax == -1)
        b_exit = (bx == -1)
        if not a_exit:
            a_exit = (grid[ax][ay] == '@')
        if not b_exit:
            b_exit = (grid[bx][by] == '@')

        if a_exit and b_exit:
            print(step)
            return

        # 扩展四个方向
        for dx, dy in dirs:
            nax, nay = ax, ay
            nbx, nby = bx, by

            if not a_exit:
                nax, nay = ax+dx, ay+dy
                if not (0<=nax<n and 0<=nay<m) or grid[nax][nay]=='#':
                    continue
            else:
                nax, nay = -1, -1

            if not b_exit:
                nbx, nby = bx-dx, by-dy
                if not (0<=nbx<n and 0<=nby<m) or grid[nbx][nby]=='#':
                    continue
            else:
                nbx, nby = -1, -1

            key = (nax, nay ,nbx, nby)

            if key not in visited:
                visited.add(key)
                q.append((nax, nay, nbx, nby, step+1))

    # 无解
    print(-1)

if __name__ == "__main__":
    tokens = sys.stdin.read().split()
    if not tokens:
        sys.exit(0)
    solve_dual_maze_packed(tokens)

发表于 2025-08-21 13:11:56 回复(0)
牛客242693846号头像 牛客242693846号
我拿python写怎么做都超时，等个大神来份python代码
发表于 2025-07-29 08:34:13 回复(0)
提交观点

问题信息

广度优先搜索(BFS)
来自：华为机试编程模拟题8
难度：
2条回答 190浏览

热门推荐

相关试题

ACM中的AC题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号