ACM中的AC题_

$\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)$ 处为平地。

Python3

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)

牛客879509792号

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_N 105 #define MAX_M 105 #define QUEUE_SIZE 1000000 #define HASH_BASE 1000003 // 方向数组：上下左右 int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // BFS 队列节点：存储A、B的坐标和步数 typedef struct { int ax, ay; // A的坐标，-1表示已离开 int bx, by; // B的坐标，-1表示已离开 int step; // 当前步数 } Node; Node queue[QUEUE_SIZE]; int q_front, q_rear; // 哈希表：用于标记状态是否已访问，避免重复搜索 typedef struct HashNode { int ax, ay, bx, by; struct HashNode *next; } HashNode; HashNode *hash_table[HASH_BASE]; char grid[MAX_N][MAX_M]; int n, m, sx, sy; // 哈希函数：将四元组(ax,ay,bx,by)映射为哈希值 int hash_func(int ax, int ay, int bx, int by) { long long val = (long long)(ax + 1) * (MAX_M + 2) * (MAX_N + 2) * (MAX_M + 2) + (long long)(ay + 1) * (MAX_N + 2) * (MAX_M + 2) + (long long)(bx + 1) * (MAX_M + 2) + (by + 1); return val % HASH_BASE; } // 检查状态是否已访问 int is_visited(int ax, int ay, int bx, int by) { int idx = hash_func(ax, ay, bx, by); HashNode *p = hash_table[idx]; while (p != NULL) { if (p->ax == ax && p->ay == ay && p->bx == bx && p->by == by) { return 1; } p = p->next; } return 0; } // 标记状态为已访问 void mark_visited(int ax, int ay, int bx, int by) { int idx = hash_func(ax, ay, bx, by); HashNode *node = (HashNode *)malloc(sizeof(HashNode)); node->ax = ax; node->ay = ay; node->bx = bx; node->by = by; node->next = hash_table[idx]; hash_table[idx] = node; } // 队列操作：入队 void queue_push(Node node) { if ((q_rear + 1) % QUEUE_SIZE != q_front) { queue[q_rear] = node; q_rear = (q_rear + 1) % QUEUE_SIZE; } } // 队列操作：出队 Node queue_pop() { Node node = queue[q_front]; q_front = (q_front + 1) % QUEUE_SIZE; return node; } // 队列判空 int queue_empty() { return q_front == q_rear; } // 初始化队列和哈希表 void init() { q_front = q_rear = 0; memset(hash_table, 0, sizeof(hash_table)); } // 释放哈希表内存 void free_hash() { for (int i = 0; i < HASH_BASE; i++) { HashNode *p = hash_table[i]; while (p != NULL) { HashNode *tmp = p; p = p->next; free(tmp); } } } // 检查坐标是否合法（在地图内且不是陷阱） int is_valid(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m) { return 0; } return grid[x][y] != '#'; } // 单人BFS：当一人离开后，计算另一人到最近传送门的步数 int single_bfs(int x, int y) { if (grid[x][y] == '@') { return 0; } int visited[MAX_N][MAX_M]; memset(visited, 0, sizeof(visited)); Node q_single[QUEUE_SIZE]; int qf = 0, qr = 0; q_single[qr++] = (Node){x, y, 0, 0, 0}; visited[x][y] = 1; while (qf < qr) { Node curr = q_single[qf++]; for (int i = 0; i < 4; i++) { int nx = curr.ax + dirs[i][0]; int ny = curr.ay + dirs[i][1]; if (is_valid(nx, ny) && !visited[nx][ny]) { if (grid[nx][ny] == '@') { return curr.step + 1; } visited[nx][ny] = 1; q_single[qr++] = (Node){nx, ny, 0, 0, curr.step + 1}; } } } return -1; } int solve() { init(); int sx0 = sx - 1; int sy0 = sy - 1; // 初始状态：两人都在起点，步数为0 Node start = {sx0, sy0, sx0, sy0, 0}; queue_push(start); mark_visited(sx0, sy0, sx0, sy0); while (!queue_empty()) { Node curr = queue_pop(); int ax = curr.ax; int ay = curr.ay; int bx = curr.bx; int by = curr.by; int step = curr.step; // 判断是否两人都已离开 if (ax == -1 && bx == -1) { return step; } // 情况1：两人都未离开，必须反向移动 if (ax != -1 && bx != -1) { for (int i = 0; i < 4; i++) { int dx = dirs[i][0]; int dy = dirs[i][1]; // A 向 (dx, dy) 移动，B 向 (-dx, -dy) 移动 int nax = ax + dx; int nay = ay + dy; int nbx = bx - dx; int nby = by - dy; int a_exit = 0, b_exit = 0; // 检查A的移动结果 if (!is_valid(nax, nay)) { continue; } if (grid[nax][nay] == '@') { a_exit = 1; nax = -1; nay = -1; } // 检查B的移动结果 if (!is_valid(nbx, nby)) { continue; } if (grid[nbx][nby] == '@') { b_exit = 1; nbx = -1; nby = -1; } // 检查状态是否已访问 if (!is_visited(nax, nay, nbx, nby)) { mark_visited(nax, nay, nbx, nby); queue_push((Node){nax, nay, nbx, nby, step + 1}); } } } // 情况2：只有A未离开，单人自由移动 else if (ax != -1) { int single_step = single_bfs(ax, ay); if (single_step != -1) { return step + single_step; } } // 情况3：只有B未离开，单人自由移动 else if (bx != -1) { int single_step = single_bfs(bx, by); if (single_step != -1) { return step + single_step; } } } free_hash(); return -1; } int main() { scanf("%d %d %d %d", &n, &m, &sx, &sy); for (int i = 0; i < n; i++) { scanf("%s", grid[i]); } int result = solve(); printf("%d\n", result); return 0; }

编辑于 2026-01-10 21:12:54 回复(0)

牛客242693846号

我拿python写怎么做都超时，等个大神来份python代码

发表于 2025-07-29 08:34:13 回复(0)

ACM中的AC题

输入描述:

输出描述:

输入

输出

说明

输入

输出

输入

输出

说明

备注:

问题信息

热门推荐

相关试题