怎么选一个适合自己的网站,网站发布时间更改,最好的购物网站排名,鄂尔多斯市建设厅官方网站1 /*2 这是我做过的一道新类型的搜索题#xff01;从来没想过用四维数组记录状态#xff01;3 以前做过的都是用二维的#xff01;自己的四维还是太狭隘了.....4 5 题意#xff1a;悟空救师傅 #xff01; 在救师父之前要先把所有的钥匙找到#xff01;6… 1 /*2 这是我做过的一道新类型的搜索题从来没想过用四维数组记录状态3 以前做过的都是用二维的自己的四维还是太狭隘了.....4 5 题意悟空救师傅 在救师父之前要先把所有的钥匙找到6 每种钥匙有 k 种 每一种有多个 只要求找到每一种的其中一个就可以7 找钥匙的顺序按照 第1种 第2种 第3种 ....第k种 8 找钥匙的时间是一步 走到相邻空地的时间是一步 打蛇的时间就是两步9 求找到师傅的最少步数 10 11 这里说一下 state[N][N][10][35]表示的含义 -state[x][y][i][j] 12 前两维就不用说了就是地图上的坐标 第三维表示的是当前找到第几把钥匙13 第四维表示的沿着一条路径走到 x, y找到 第 i 把钥匙打掉了哪几条蛇14 将 j 拆分成 二进制 从右往左数 如果第 k 为是1 表示第 k 条 蛇杀掉了 15 */ 16 17 #includeiostream18 #includecstdio19 #includecstring20 #includealgorithm21 #includequeue22 23 #define N 10524 using namespace std;25 26 char mp[105][105];27 28 bool state[N][N][10][35];29 30 int bx, by;31 32 struct node{33 int x, y;34 int numk, snk;35 int step;36 node(){}37 38 node(int x, int y, int numk, int snk, int step){39 this-x x;40 this-y y;41 this-numk numk;42 this-snk snk;43 this-step step;44 }45 };46 47 int n, m;48 int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1};49 bool operator (node a, node b) {50 return a.step b.step;51 }52 53 priority_queuenodeq;54 55 bool bfs(){56 while(!q.empty()) q.pop();57 memset(state, false, sizeof(state));58 q.push( node(bx, by, 0, 0, 0) );59 state[bx][by][0][0] true;60 while( !q.empty() ) {61 node cur q.top();62 q.pop();63 for(int i0; i4; i){64 int x cur.x dir[i][0];65 int y cur.y dir[i][1];66 if(x1 || xn || y1 || yn || mp[x][y]#) continue;67 int numk cur.numk, snk cur.snk, step cur.step;68 if(mp[x][y] .)69 step 1;70 else if( mp[x][y] 1 mp[x][y] 9){71 if( numk 1 mp[x][y] - 0 )72 numk 1;73 step 1;74 }75 else if( mp[x][y] A mp[x][y] E ){//这一步是关键 76 int cnt mp[x][y] - A 1; 77 if( (1 (cnt-1) ) snk ) step 1;//如果这一条蛇已经被打过了也就是一条路又折回到这一个点 78 else{//在这一条路上这条蛇没有被打过那就将它打掉并标记这条蛇打过了 79 step 2;80 snk ^ ( 1 (cnt-1) );81 }82 }83 else if( mp[x][y] T numk m ){84 printf(%d\n, step 1);85 return true;86 }87 else step 1;88 89 if( state[x][y][numk][snk] ) continue;90 state[x][y][numk][snk] true;91 q.push( node(x, y, numk, snk, step) );92 }93 }94 return false;95 }96 97 int main(){98 while( scanf(%d%d, n, m) (n ||m) ) {99 int cntS 0;
100 for(int i 1; i n; i){
101 scanf(%s, mp[i] 1);
102 for(int j 1; j n; j)
103 if(mp[i][j] K){
104 bx i;
105 by j;
106 }
107 else if(mp[i][j] S)
108 mp[i][j] A cntS;
109 }
110 if( !bfs() ) printf(impossible\n);
111 }
112 return 0;
113 } 转载于:https://www.cnblogs.com/hujunzheng/p/3984954.html
