邻接网格
* * * *
拉格朗日计划
* * * *
邻接网格

现有一系列用9行字符串表示的$9\times 9$网格,表示其中“#”表示墙,“0”表示能量源,“-”表示可以通过的点。

对每个网格,计算出每个可通过点到最近的能量源的最短路径的长度。路径由横向或纵向移动组成,每步移动一格,长度就是到达能量源所需要移动的步数,墙无法通过。

把输入字符串中的“-”替换为上述最短路径的长度,该长度用一个62进制数表示(0-9A-Za-z依次表示0-61)。无法连同到能量源的点所对应的字符无需替换。

本题难度:



解答

使用广度优先搜索,先找出能量源列表,更新其周围一格,再更新其周围两个。。。以此类推直至结束,此处用了比较多的短码技巧。

最终代码有七行。

代码长度:257字节 vs. 全站第一:140字节。

import sys,string as s
for a in sys.argv[1:]:
  r,i=[c for c in range(89)if a[c]=="0"],1
  while r:=[j for c in r for j in[c+(c%10<8),c-(c%10>0),c+10*(c<80),c-10*(c>9)]if a[j]=="-"]:
   for c in r:a=a[:c]+s.printable[i].swapcase()+a[c+1:]
   i+=1
  print(a+"\n")