便宜的vps租用网站,湖北网站开发,长垣县做网站的,西安建设工程交易网2012-08-11 我的第一个A*算法#xff1a; 四处看A*算法。。还是有一点没有弄明白就是那个当已经在列表中的时候再次进入的时候怎么去更新。 这道题。。有点难开始的时候不会位压缩#xff0c;去看了一个别人的代码。所以感谢一下。这位高手。写了一个bfs(),500多ms。 看了A*…2012-08-11 我的第一个A*算法 四处看A*算法。。还是有一点没有弄明白就是那个当已经在列表中的时候再次进入的时候怎么去更新。 这道题。。有点难开始的时候不会位压缩去看了一个别人的代码。所以感谢一下。这位高手。写了一个bfs(),500多ms。 看了A*算法后用A*算法去改进了一下。跑到了360ms很高兴。。所以写了一下作为学A*算法的一个纪念 View Code 1 #includeiostream2 #includecstdio3 #includecstring4 #includequeue5 using namespace std;6 char sign[21][21][16385];7 char map[21][25];8 int m,n,L,k;9 int maxstep;10 int minstep;11 struct node12 {13 int xi,xj;14 };15 node pt[10];16 int f[4][2]{{-1,0},{1,0},{0,-1},{0,1}};17 struct stem18 {19 int xi,xj;20 int state;21 int h,f,g;22 bool operator(const stem a)const23 {24 return fa.f; 25 }26 }u,v,w;27 void setmap(node *_pt)28 {29 int i;30 for(i1;iL;i)31 {32 map[_pt[i].xi][_pt[i].xj]1;33 }34 }35 void clearmap(node *_pt)36 {37 int i;38 for(i1;iL;i)39 map[_pt[i].xi][_pt[i].xj]0;40 }41 int bfs(char stone[][25])42 {43 priority_queuestemq;44 w.xi1;45 w.xj1;46 w.g0;47 w.fpt[0].xipt[0].xj-2;48 w.hpt[0].xipt[0].xj-2;49 q.push(w);50 int i,j;51 while(!q.empty())52 {53 uq.top();54 q.pop();55 for(i0;i4;i)56 {57 v.xiu.xif[i][0];58 v.xju.xjf[i][1];59 if(v.xi1||v.xin||v.xj1||v.xjm)continue;60 if(stone[v.xi][v.xj])continue; 61 stone[v.xi][v.xj]1;62 v.gu.g1;63 v.hpt[0].xi-v.xipt[0].xj-v.xj;64 v.fv.gv.h;65 if(v.xipt[0].xiv.xjpt[0].xj)return v.f;66 q.push(v); 67 }68 }69 return -1;70 }71 void getmaxmin()72 {73 char stone[21][25];74 memcpy(stone,map,sizeof(map));75 minstepbfs(stone);76 if(minstep-1)return ;77 setmap(pt);78 memcpy(stone,map,sizeof(map));79 maxstepbfs(stone);80 clearmap(pt);81 if(maxstep-1)maxstep0xffff;82 return ;83 }84 int getstate()85 {86 int stem;int i;87 88 stem0;89 for(i1;iL;i)90 {91 stem2;92 if(pt[i].xipt[i-1].xi)stem|0;93 else if(pt[i].xipt[i-1].xi) stem|1;94 else if(pt[i].xjpt[i-1].xj) stem|2;//以前面一位作为标准 95 else 96 stem|3;97 }98 99 return stem;
100 }
101 void getcord(int x,int y,int state)
102 {
103 pt[0].xix;
104 pt[0].xjy;
105 int manx;
106 int step;
107 int i;manx3;
108 for(i1;iL;i)
109 {
110 step(state((L-i-1)*2))manx;
111 if(step0) x;
112 else if(step1) x--;
113 else if(step2) y;
114 else if(step3) y--;
115 pt[i].xix;
116 pt[i].xjy;
117 }
118 return ;
119 }
120 int bfs()
121 {
122 int i;
123 priority_queuestemq;
124 w.xipt[0].xi;
125 w.xjpt[0].xj;
126 w.g0;
127 w.fpt[0].xipt[0].xj-2;
128 w.hpt[0].xipt[0].xj-2;
129 w.stategetstate();
130 q.push(w);
131 while(!q.empty())
132 {
133 uq.top();q.pop();
134 getcord(u.xi,u.xj,u.state);
135 setmap(pt);
136 for(i0;i4;i)
137 {
138 v.xiu.xif[i][0];
139 v.xju.xjf[i][1];
140 if(v.xi1||v.xin||v.xj1||v.xjm)continue;
141 if(map[v.xi][v.xj])continue;
142 if(u.g1v.xiv.xj-2maxstep)continue;
143 v.state((u.state2)|(i(L-2)*2));
144 if(sign[v.xi][v.xj][v.state])continue;
145 sign[v.xi][v.xj][v.state]1;
146 v.gu.g1;
147 v.hv.xiv.xj-2;
148 v.fv.gv.h;
149 if(v.xi1v.xj1)return v.f;
150 q.push(v);
151 }
152 clearmap(pt);
153 }
154 return -1;
155 }
156 int main()
157 {
158 int i;
159 int cas;
160 cas0;
161 while(scanf(%d%d%d,n,m,L)(nmL))
162 {
163 cas;
164 int x,y;
165 maxstep0;
166 minstep0;
167 for(i0;iL;i)
168 {
169 scanf(%d%d,pt[i].xi,pt[i].xj);
170 }
171 scanf(%d,k);
172 memset(map,0,sizeof(map));
173 memset(sign,\0,sizeof(sign));
174 for(i0;ik;i)
175 {
176 scanf(%d%d,x,y);
177 map[x][y]1;
178 }
179 printf(Case %d: ,cas);
180 getmaxmin();
181 if(pt[0].xi1pt[0].xj1)printf(0\n);
182 else if(minstep-1)printf(-1\n);
183 else if(minstepmaxstep)printf(%d\n,minstep);
184 else printf(%d\n,bfs());
185 }
186 return 0;
187 } 最后就是继续努力。。转载于:https://www.cnblogs.com/qq774550/archive/2012/08/11/2633744.html
