简答题 偏难
#7251

哥斯拉大战金刚 众所周知,哥斯拉和金刚是时代仇敌,大战一触即发。金刚为了打败哥斯拉,要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图,S表…

哥斯拉大战金刚

众所周知,哥斯拉和金刚是时代仇敌,大战一触即发。金刚为了打败哥斯拉,要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图,S表示金刚目前的位置,T表示地心空洞的入口,X表示障碍物,.表示平地。在前往地心空洞之前,金刚必须先获得一系列打开地心空洞的钥匙(在地图上通过数字1,2,…,k表示),并且获得i类钥匙的前提是金刚已经获得了1,2,…,i-1类钥匙,金刚在拿到地图上所有种类的钥匙之后即可前往地心空洞的入口。另外,同一种类的钥匙可能有多把,金刚只需获得其中任意一把即可。金刚每一步可以朝上下左右四个方向中的一个移动一格,值得注意的是,哥斯拉为了阻挠金刚的计划,还在地图上设置了q个陷阱(在网格图中用G表示),金刚第一次进入某个陷阱需要花费额外的一步来破坏陷阱(这之后该陷阱即可被视为平地)。为了更好的掌握全局,请你帮金刚计算到达地心空洞入口所需要花费的最少步数。输入数据保证有解。

时间限制:6000

内存限制:262144

输入

第一行输入两个整数n,m,表示网格图的大小。 接下来n行,每行输入m个字符,表示地图 1 ≤ n,m ≤ 100 1 ≤ k ≤ 9 1 ≤ q ≤ 7

输出

输出一行包含一个整数,表示金刚到达地心空洞入口所需要花费的最少步数。


样例输入

5 5
XX13X
X.GXX
S...T
XXGXX
....2

样例输出

24
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;vector&gt; using namespace std; struct point {   int x, y;   short keys;   short fighted;   int steps;   short layout;   point(int inx, int iny, short k, short f, int s, short l)       : x(inx), y(iny), keys(k), fighted(f), steps(s), layout(l) {} }; char flags[105][105][10][130]; int n, m; int k, q; char maze[105][105]; vector&lt;pair&lt;int, int&gt;&gt; traps; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int findTraps(int x, int y) {   for (int i = 0; i &lt; q; i++) {     if (traps[i].first == x &amp;&amp; traps[i].second == y)       return i;   } } int main() {   cin &gt;&gt; n &gt;&gt; m;   int startx, starty;   q = 0;   k = 0;   for (int i = 0; i &lt; n; i++) {     for (int j = 0; j &lt; m; j++) {       cin &gt;&gt; maze[i][j];       if (maze[i][j] == 'S') {         startx = i;         starty = j;       }       if (maze[i][j] == 'G') {         q++;         traps.push_back(make_pair(i, j));       }       if (maze[i][j] &gt; '0' &amp;&amp; maze[i][j] &lt;= '9')         k = max(k, maze[i][j] - '0');     }   }   queue&lt;point&gt; myqueues;   short oriLayout = (1 &lt;&lt; q) - 1;   myqueues.push(point(startx, starty, 0, 0, 0, oriLayout));   memset(flags, 0, sizeof(flags));   flags[startx][starty][0][oriLayout] = 1;   while (!myqueues.empty()) {     point top = myqueues.front();     myqueues.pop();     if (maze[top.x][top.y] == 'T' &amp;&amp; top.keys == k) {       cout &lt;&lt; top.steps &lt;&lt; endl;       break;     }     if (maze[top.x][top.y] == 'G' &amp;&amp; top.fighted == 0) {       int index = findTraps(top.x, top.y);       short layout = top.layout &amp; (~(1 &lt;&lt; index));       myqueues.push(point(top.x, top.y, top.keys, 1, top.steps + 1, layout));       flags[top.x][top.y][top.keys][layout] = 1;       continue;     }     for (int i = 0; i &lt; 4; i++) {       int tx = top.x + dx[i];       int ty = top.y + dy[i];       if (tx &lt; 0 || tx &gt;= n || ty &lt; 0 || ty &gt;= m)         continue;       if (maze[tx][ty] == 'X')         continue;       else if (maze[tx][ty] == 'G') {         if (flags[tx][ty][top.keys][top.layout])           continue;         int index = findTraps(tx, ty);         if ((top.layout &gt;&gt; index) &amp; 1) // 还没打           myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));         else           myqueues.push(point(tx, ty, top.keys, 1, top.steps + 1, top.layout));         flags[tx][ty][top.keys][top.layout] = 1;       } else if (maze[tx][ty] == '.' || maze[tx][ty] == 'S' ||                  maze[tx][ty] == 'T') {         if (flags[tx][ty][top.keys][top.layout])           continue;         myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));         flags[tx][ty][top.keys][top.layout] = 1;       } else {         int key = maze[tx][ty] - '0';         if (key == top.keys + 1) {           if (flags[tx][ty][key][top.layout])             continue;           myqueues.push(point(tx, ty, key, 0, top.steps + 1, top.layout));           flags[tx][ty][key][top.layout] = 1;         } else {           if (flags[tx][ty][top.keys][top.layout])             continue;           myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));           flags[tx][ty][top.keys][top.layout] = 1;         }       }     }   }   return 0; }</pre>
解析

解题思路

思路:广搜题,属于较为复杂的一种,既要收集钥匙也要破坏陷阱。

状态包括:x,y坐标,keys表示现在收集的钥匙种数,fighted表示是否已经消灭陷阱,steps记录此时的步数,layout是陷阱的分布(用short变量表示)。

去重:xy坐标+钥匙+陷阱分布

地图上的标识有

‘.’:平地;‘X’:障碍,不能通过;‘T’:终点;‘S’:起点;‘G’:陷阱;1~9的数字:钥匙

起点和没有拿完钥匙的终点,不能拿的钥匙,破坏完的陷阱都当做平地处理