简答题 偏难
#7121

密室逃脱 小Y喜欢玩密室逃脱,每次游戏开始时,小Y会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明,解开线索对她来说并不难,但是她有…

密室逃脱

小Y喜欢玩密室逃脱,每次游戏开始时,小Y会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明,解开线索对她来说并不难,但是她有一点懒,她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。

密室是m行n列的格子矩阵,小Y从左上角(1,1)进入密室,密室中有三种格子:

墙,以数字0标记

路,以数字1标记

隐藏线索处,以数字( > 1)标记, 代表该线索的难度

小Y需要按照难度递增的顺序解开各个线索,逃脱密室。

时间限制:1000

内存限制:65536

输入

第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的游戏中小Y所处的密室。 对于每组数据,第一行包括两个整数:m(1 <= m <= 100)、n(1 <= n <= 100)。 接下来 m 行,每行有n个数字,第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。 题目保证进入密室处(1,1)不是墙壁,线索的难度都不相同。

输出

对于每组数据,你需要输出一个整数,表示小Y在这个密室中至少要移动多少次才能成功通关。 如果小Y不可能解开所有线索,输出-1.

样例输入

2
3 3
1 3 2
1 0 4
10 6 5
3 3
1 3 2
0 0 0
10 6 5

样例输出

8
-1

提示

样例解释:由于需要按难度顺序解开线索,在第一组数据中,小Y第一次移动到3时不能解密,在完成2之后需要回到3.最后小Y解开10时,她成功通关。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//示例代码 条件+广搜 #include &lt;iostream&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; #include &lt;queue&gt;   using namespace std; int m,n; int maze[104][104] = {};   int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; bool legal(int x, int y){     if(0 &lt;= x &amp;&amp; x&lt; m &amp;&amp; 0 &lt;= y &amp;&amp; y &lt; n &amp;&amp; maze[x][y] != 0)return 1;     return 0; } struct Node{     int x, y, k, t; }; int main() {     int T;     cin &gt;&gt; T;     while(T--){         memset(maze, 0, sizeof(maze));         int vis[104][104] = {};         memset(vis, 0xff, sizeof(vis));         int S[10050] = {};         int cnt = 0;         cin &gt;&gt; m &gt;&gt; n;         for(int i = 0; i &lt; m; ++i){             for(int j = 0; j &lt; n; ++j){                 cin &gt;&gt; maze[i][j];                 if (maze[i][j] &gt; 1) {                     S[cnt++] = maze[i][j];                 }             }         }         queue&lt;Node&gt; open;         sort(S, S + cnt);         if (maze[0][0] == S[0]) {             open.push({0, 0, 1, 0});             vis[0][0] = 1;         }         else {             open.push({0, 0, 0, 0});             vis[0][0] = 0;         }         bool flag = 0;                while (!open.empty()) {             Node temp = open.front();             open.pop();             if (temp.k == cnt) {                 flag = 1;                 cout &lt;&lt; temp.t &lt;&lt; endl;                 break;             }             for (int i = 0; i &lt; 4; i++) {                 int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;                 if (!legal(x,y)) continue;                 if (maze[x][y] == S[k]) k++;                 if (vis[x][y] &gt;= k) continue;                 vis[x][y] = k;                 open.push({x, y, k, temp.t + 1});             }         }         if (!flag) cout &lt;&lt; -1 &lt;&lt; endl;     }     return 0; }</pre>
这道题暂未补解析。