A*イニシアチブ検索テンプレート
ブロガー自身は自分のレベルを上げたいと思っていたので、以前から難しいと思っていたA*啓発的な検索を書いて、1時間以上仕事を頑張りました.やっとこのような気持ち悪いプログラムのデバッグが完成しました(私に啓発的な検索が何なのか聞かないでください.ネット上には、ブロガーはみんなに参考コードを提供しただけです).このコードには注釈があり、テストに合格しました(最末端にブロガーのテストデータの一つがあります).そのために向上してほしいです.
/*
ID: ljf_cnyali
PROG: A*
LANG: C++
*/
#include
using namespace std;
#define REP(i, a, b) for(int i = (a), _end_ = (b);i <= _end_; ++ i)
#define mem(a) memset((a), 0, sizeof(a))
#define str(a) strlen(a)
const int maxn = 1010;
int Row, Col;//
struct block {
int f, g, h, Fx, Fy, Mx, My;//F = G + H, Fx, Fy , Mx, My
};
int dt[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};//east, south, north, west
struct block Open[maxn], Close[maxn];//
int Startx, Starty, Endx, Endy;//
int Map[maxn][maxn];// , 1
int CountOpen, CountClose;//
void INIT() {
scanf("%d%d", &Row, &Col);
REP(i, 0, Row - 1)
REP(j, 0, Col - 1)
scanf("%d", &Map[i][j]);
scanf("%d%d%d%d", &Startx, &Starty, &Endx, &Endy);
}
int getG(int x, int y) {
return abs(x - Startx) + abs(y - Starty);
}
int getH(int x, int y) {
return abs(x - Endx) + abs(y - Endy);
}
void InOpen(int Fx, int Fy, int Mx, int My) {
Open[CountOpen].g = getG(Mx, My);
Open[CountOpen].h = getH(Mx, My);
Open[CountOpen].f = Open[CountOpen].g + Open[CountOpen].h;
Open[CountOpen].Fx = Fx;
Open[CountOpen].Fy = Fy;
Open[CountOpen].Mx = Mx;
Open[CountOpen].My = My;
++CountOpen;
}
void DeleteOpen(int index) {
REP(i, index, CountOpen - 1)
Open[i] = Open[i + 1];
--CountOpen;
}
void InClose(int index) {
Close[CountClose] = Open[index];
++CountClose;
DeleteOpen(index);// index Open
}
void PrintfPath() {
int ans = 0;
//
int Fx = Close[CountClose - 1].Fx;
int Fy = Close[CountClose - 1].Fy;
// ,
for(int i = CountClose - 1;i >= 0; -- i)
if(Close[i].Mx == Fx && Close[i].My == Fy) {
printf("Result: %d, %d
", Fx, Fy);
Fx = Close[i].Fx;
Fy = Close[i].Fy;
++ans;
}
printf("%d
", ans);//
}
int SearchRound(int x, int y) {
bool flag;
REP(i, 0, 3) {
int dx = dt[i][0] + x;
int dy = dt[i][1] + y;
flag = true;
// Open :Close 、Open 、 、 Open
//Close Open
REP(j, 0, CountClose - 1)
if(dx == Close[j].Mx && dy == Close[j].My) {
flag = false;
break;
}
REP(j, 0, CountOpen - 1)
if(dx == Open[j].Mx && dy == Open[j].My) {
flag = false;
break;
}
if(Map[dx][dy] == 1)
flag = false;
// flag , Open
if(flag)
InOpen(x, y, dx, dy);
//
if(dx == Endx && dy == Endy)
return 1;
}
return 0;
}
void ShorestPath() {
int x = Startx, y = Starty, k;
//
Open[CountOpen].g = getG(x, y);// G(x, y)
Open[CountOpen].h = getH(x, y);// H(x, y)
Open[CountOpen].f = Open[CountOpen].g + Open[CountOpen].h;// F(x, y)
Open[CountOpen].Fx = -1;
Open[CountOpen].Fy = -1;
Open[CountOpen].Mx = x;
Open[CountOpen].My = y;
++CountOpen;//
// Open F
while(1) {
int min = 1000000000, index = 0;
REP(i, 0, CountOpen - 1)
if(Open[i].f < min) {
min = Open[i].f;
index = i;
}
// F Close
InClose(index);
int flag = SearchRound(Close[CountClose - 1].Mx, Close[CountClose - 1].My);//
if(flag == 1) {
InClose(CountOpen - 1);// Close
PrintfPath();// ,
break;
}
}
}
int main() {
// freopen("A*.in", "r", stdin);
// freopen("A*.out", "w", stdout);
INIT();//
ShorestPath();//
return 0;
}
/*
8 9
1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1
1 0 1 0 1 0 0 0 1
1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1
4 2 1 7
*/