拯救公主 计蒜客 BFS+二进制状压

Problem Description

多灾多难的公主又被大魔王抓走啦！国王派遣了第一勇士蒜头君去拯救她。身为超级厉害的术士，同时也是蒜头君的好伙伴，你决定祝他一臂之力。你为蒜头君提供了一张大魔王根据地的地图，上面标记了蒜头君和公主所在的位置，以及一些不能够踏入的禁区。你还贴心地为蒜头君制造了一些传送门，通过一个传送门可以瞬间转移到任意一个传送门，当然蒜头君也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外，你还查探到公主所在的地方被设下了结界，需要集齐 K(0≤K≤5) 种宝石才能打开。当然，你在地图上也标记出了不同宝石所在的位置。你希望蒜头君能够带着公主早日凯旋。于是在蒜头君出发之前，你还需要为蒜头君计算出他最快救出公主的时间。地图用一个 R×C 的字符矩阵来表示。字符 S 表示蒜头君所在的位置，字符 E 表示公主所在的位置，字符 # 表示不能踏入的禁区，字符 “$” 表示传送门，字符 . 表示该位置安全，数字字符 0 至 4 表示了宝石的类型。蒜头君每次可以从当前的位置走到他上下左右四个方向上的任意一个位置，但不能走出地图边界。蒜头君每走一步需要花费 1 个单位时间，从一个传送门到达另一个传送门不需要花费时间。当蒜头君走到宝石所在的位置时，就视为得到了该宝石，不需要花费额外时间。

输入格式

第一行是一个正整数 T(1≤T≤10)，表示一共有 T 组数据。 每一组数据的第一行包含了三个用空格分开的正整数 R、C（2≤R,C≤200) 和 K，表示地图是一个 R×C的矩阵，而蒜头君需要集齐 K 种宝石才能够打开拘禁公主的结界。 接下来的 R 行描述了地图的具体内容，每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。$ 的数量不超过 10 个。宝石的类型在数字 0 至 4 范围内，即不会超过 5 种宝石。

输出格式

对于每一组数据，输出蒜头君救出公主所花费的最少单位时间。若蒜头君无法救出公主，则输出 “oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。

样例输入

1
7 8 2
........
..S..#0.
.##..1..
.0#.....
...1#...
...##E..
...1....
123456789

样例输出

11

Problem Analysis

给定字符矩阵， S S S表示起点， E E E表示终点， 1 − K 1 - K 1−K表示宝石点，$ 表示传送门。求从起点出发，收集全部的宝石并到达终点的最短路长度。

1.首先分析宝石的处理办法：首先我们选择了广搜，那么在搜索的过程中是不可能回溯的，因此对于当前搜到的点，其历史路径上具有的宝石数目唯一确定，因此对于每一个点，我们增设一个属性 g e m gem gem表示“搜到当前的点为止，已经获得的宝石数目”，同时给访问数组增加一个维度，宝石最多会有 5 5 5种，第三维度的大小需要 1 < < 5 1