求问一道题的思路
  • 板块题目总版
  • 楼主caramel_qwq
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/7/26 15:10
  • 上次更新2023/10/27 18:19:47
查看原帖
求问一道题的思路
444195
caramel_qwq楼主2022/7/26 15:10
一个迷宫,用 N*N 的网格表示(2≤N≤100), K 个人,分散在这些 N*N 的某一个格子里面,没有两个人在一个格子里。

一般情况下,每个人都可以选择往他的上下左右四个方向移动,但是某些格子之间有墙, 没有人可以穿过墙, 一共 R 个墙。

定义两个人(一对人)是“隔离”的就是说不穿墙的情况下,其中 1 个人无法走到另外 1 个人所在的格子。问一共
多少对“隔离”的人。 (1≤K,R≤N^2)

蒟蒻现在写的O(Kn^2)解,太菜了,有没有更快的解法?教练只给了一个连通性的提示

2022/7/26 15:10
加载中...