小丫喜欢玩密室逃脱,每次游戏开始时,小丫会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。
小Y非常聪明,解开线索对她来说并不难,但是她有一点懒,她希望在通关过程中移动次数最少。请你帮小丫计算她至少要移动多少次才能成 功通关。
密室是m 行n列的格子矩阵,小Y从左上角(1,1)进入密室,密室中有三种格子: 墙,以数字0标记 路,以数字1标记 隐藏线索处,以数字(> 1)标记,代表该线索的难度 小Y需要按照难度递增的顺序解开各个线索,逃脱密室。
时间限制:1000
内存限制:65536
输入第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的游戏中小Y所处的密室。
对于每组数据,第一行包括两个整数:m(1 n;for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){cin >> maze[i][j];if (maze[i][j] > 1) {nanduS[cnt++] = maze[i][j];}}}queue open;sort(nanduS, nanduS + cnt); // 对难度数据进行从小到大排序// 起始点如果是要解开线索的第一个密室,设置k=1,否则设置k=0;(k代表k难度有没有在该密室被搜索过)if (maze[0][0] == nanduS[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