360做企业网站多少钱,凡客诚品网,做门户网站啥意思,电子商务网站建设的代码3A的题目#xff0c;第一次TLE#xff0c;是因为一次BFS起点到终点状态太多爆掉了时间。 第二次WA#xff0c;是因为没有枚举蛇的状态。 解体思路#xff1a; 因为蛇的数目是小于5只的#xff0c;那就首先枚举是否杀死每只蛇即可。 然后多次BFS#xff0c;先从起点到第一…3A的题目第一次TLE是因为一次BFS起点到终点状态太多爆掉了时间。 第二次WA是因为没有枚举蛇的状态。 解体思路 因为蛇的数目是小于5只的那就首先枚举是否杀死每只蛇即可。 然后多次BFS先从起点到第一把钥匙不能往回走要用VIS数组标记。 第二次从第一把钥匙走到第二把钥匙。 最后一次从最后一把钥匙走到终点即可。 Tips 1: 在每次BFS过程中使用优先队列保证每次是最小步长的状态。 Tips2 :使用二进制枚举蛇的状态 Tips3:首先使用DFS判断是否绝对有解如果无解输出impossible如果有解则继续。 Tips4:多次 BFS,而不是一次BFS否则会导致状态太多TLE 代码如下 1 //#pragma comment(linker, /STACK:16777216) //for c Compiler2 #include stdio.h3 #include iostream4 #include cstring5 #include cmath6 #include stack7 #include queue8 #include vector9 #include algorithm10 #define ll long long11 #define Max(a,b) (((a) (b)) ? (a) : (b))12 #define Min(a,b) (((a) (b)) ? (a) : (b))13 #define Abs(x) (((x) 0) ? (x) : (-(x)))14 using namespace std;15 16 const int INF 0x3f3f3f3f;17 const int MAXN 220;18 const double eps 1e-9;19 20 struct node{21 int x,y,step;22 };23 24 char map[105][105];25 int vis[105][105];26 int to[4][2] {1,0,-1,0,0,1,0,-1};27 int n,m,sx,sy,ex,ey,ans;28 29 bool operator (node a, node b){30 return a.step b.step;31 }32 33 int check(int x,int y){34 if(x0 || xn || y0 || yn)35 return 1;36 if(map[x][y]# || vis[x][y])37 return 1;38 return 0;39 }40 41 void bfs(int sx, int sy, int k){42 int i;43 priority_queue node Q;44 node a,next;45 a.x sx;46 a.y sy;47 a.step 0;48 vis[a.x][a.y]1;49 Q.push(a);50 while(!Q.empty()){51 a Q.top();52 //printf(x %d y %d step %d\n,a.x,a.y,a.step);53 Q.pop();54 if(k m){55 if(map[a.x][a.y] k 0){56 ans a.step;57 ex a.x;58 ey a.y;59 //printf(%d %d cur _ ans %d\n,ex, ey,ans);60 return;61 }62 } else{63 if(map[a.x][a.y] T){64 ans a.step;65 ex a.x;66 ey a.y;67 //printf(%d %d cur _ ans %d\n,ex, ey,ans);68 return;69 }70 }71 for(i 0; i4; i){72 next a;73 next.xto[i][0];74 next.yto[i][1];75 if(check(next.x,next.y)) continue;76 next.stepa.step1;77 if(map[a.x][a.y] S){78 next.step;79 }80 vis[next.x][next.y] 1;81 Q.push(next);82 }83 if(map[a.x][a.y] S){84 map[a.x][a.y] .;85 }86 }87 ans INF;88 return ;89 }90 91 void dfs(int x, int y){92 for(int i 0; i4; i){93 int _x x to[i][0];94 int _y y to[i][1];95 if(check(_x,_y)) continue;96 if(map[_x][_y] ! #){97 vis[_x][_y] 1;98 dfs(_x,_y);99 }
100 }
101 }
102 int main(){
103 int i,j,cc,s_flag;
104 while(EOF ! scanf(%d%d,n,m)){
105 if(n 0 m 0) break;
106 s_flag 0;
107 node S[6];
108 for(i 0; in; i)
109 scanf(%s,map[i]);
110 for(i 0; in; i){
111 for(j 0; jn; j){
112 if(map[i][j]K){
113 sx i;
114 sy j;
115 }else if(map[i][j] T){
116 ex i,ey j;
117 }else if(map[i][j] S){
118 S[s_flag].x i, S[s_flag].y j;
119 }
120 }
121 }
122 memset(vis,0,sizeof(vis));
123 vis[sx][sy] 1;
124 dfs(sx,sy);
125 int kkk[11];
126 bool flag false;
127 memset(kkk, 0, sizeof(kkk));
128 for(i 0; i n; i){
129 for(j 0; j n; j){
130 if(map[i][j] 1 map[i][j] 9 vis[i][j]){
131 kkk[map[i][j] - 0] 1;
132 }
133 }
134 }
135 for(i 1; i m; i){
136 if(!kkk[i]) break;
137 }
138 if(i m 1) flag true;
139
140 if(vis[ex][ey] 0 || !flag){
141 printf(impossible\n);
142 continue;
143 }
144 s_flag 0;
145 for(i 0; in; i){
146 for(j 0; jn; j){
147 if(map[i][j] S){
148 S[s_flag].x i, S[s_flag].y j;
149 }
150 }
151 }
152 int minansINF;
153 for(cc 0; cc (1 s_flag); cc){
154 ans 0;
155 for(i 0; i s_flag; i){
156 if((1 i) cc){
157 map[S[i].x][S[i].y] .;
158 ans;
159 }
160 else {
161 map[S[i].x][S[i].y] #;
162 }
163 }
164 for(i 0; i n; i){
165 for(j 0; j n; j){
166 if(map[i][j] K){
167 ex i;
168 ey j;
169 }
170 }
171 }
172 for(int k 1; k m 1; k){
173 memset(vis, 0, sizeof(vis));
174 sx ex;
175 sy ey;
176 bfs(sx, sy, k);
177 }
178 minansmin(minans,ans);
179 }
180 printf(%d\n,minans);
181 }
182 return 0;
183 } 转载于:https://www.cnblogs.com/wushuaiyi/p/3988246.html
