A*

#include 
#include 
  
#define MaxLength 100    //ó?óúó??è?óáD￡¨Open±í￡?μ?êy×é
#define Height     15    //μ?í????è
#define Width      20    //μ?í??í?è
  
#define Reachable   0    //?éò?μ?′?μ??áμ?
#define Bar         1    //??°-??
#define Pass        2    //Dèòa×?μ?2?êy
#define Source      3    //?eμ?
#define Destination 4    //??μ?
  
#define Sequential  0    //?3Dò±éàú
#define NoSolution  2    //?T?a??·?°?
#define Infinity    0xfffffff
  
#define East       (1 << 0)
#define South_East (1 << 1)
#define South      (1 << 2)
#define South_West (1 << 3)
#define West       (1 << 4)
#define North_West (1 << 5)
#define North      (1 << 6)
#define North_East (1 << 7)
  
typedef struct
{
    signed char x, y;
} Point;
  
const Point dir[8] =
{
    {0, 1},   // East
    {1, 1},   // South_East
    {1, 0},   // South
    {1, -1},  // South_West
    {0, -1},  // West
    {-1, -1}, // North_West
    {-1, 0},  // North
    {-1, 1}   // North_East
};
  
unsigned char within(int x, int y)
{
    return (x >= 0 && y >= 0
        && x < Height && y < Width);
}
  
typedef struct
{
    int x, y;
    unsigned char reachable, sur, value;
} MapNode;
  
typedef struct Close
{
    MapNode *cur;
    char vis;
    struct Close *from;
    float F, G;
    int H;
} Close;
  
typedef struct //ó??è?óáD￡¨Open±í￡?
{
    int length;        //μ±?°?óáDμ?3¤?è
    Close* Array[MaxLength];    //?à???áμ?μ?????
} Open;
  
static MapNode graph[Height][Width];
static int srcX, srcY, dstX, dstY;    //?eê?μ??￠??μ?
static Close close[Height][Width];
  
// ó??è?óáD?ù±?2ù×÷
void initOpen(Open *q)    //ó??è?óáD3?ê??ˉ
{
    q->length = 0;        // ?ó?ú?a??êy3?ê??a0
}
  
void push(Open *q, Close cls[Height][Width], int x, int y, float g)
{    //?òó??è?óáD￡¨Open±í￡??Dìí?ó?a??
    Close *t;
    int i, mintag;
    cls[x][y].G = g;    //?ùìí?ó?úμ?μ?×?±ê
    cls[x][y].F = cls[x][y].G + cls[x][y].H;
    q->Array[q->length++] = &(cls[x][y]);
    mintag = q->length - 1;
    for (i = 0; i < q->length - 1; i++)
    {
        if (q->Array[i]->F < q->Array[mintag]->F)
        {
            mintag = i;
        }
    }
    t = q->Array[q->length - 1];
    q->Array[q->length - 1] = q->Array[mintag];
    q->Array[mintag] = t;    //???à??oˉêy?μ×?D??úμ???óú?óí·
}
  
Close* shift(Open *q)
{
    return q->Array[--q->length];
}
  
// μ?í?3?ê??ˉ2ù×÷
void initClose(Close cls[Height][Width], int sx, int sy, int dx, int dy)
{    // μ?í?Close±í3?ê??ˉ????
    int i, j;
    for (i = 0; i < Height; i++)
    {
        for (j = 0; j < Width; j++)
        {
            cls[i][j].cur = &graph[i][j];        // Close±í?ù???úμ?
            cls[i][j].vis = !graph[i][j].reachable;        // ê?·?±?·??ê
            cls[i][j].from = NULL;                // ?ùà′?úμ?
            cls[i][j].G = cls[i][j].F = 0;
            cls[i][j].H = abs(dx - i) + abs(dy - j);    // ?à??oˉêy?μ
        }
    }
    cls[sx][sy].F = cls[sx][sy].H;            //?eê?μ??à??3?ê??μ
    //    cls[sy][sy].G = 0;                        //ò?2??¨·?′ú???μ
    cls[dx][dy].G = Infinity;
}
  
void initGraph(const int map[Height][Width], int sx, int sy, int dx, int dy)
{    //μ?í?·￠éú±??ˉê±??D?11?ìμ?
    int i, j;
    srcX = sx;    //?eμ?X×?±ê
    srcY = sy;    //?eμ?Y×?±ê
    dstX = dx;    //??μ?X×?±ê
    dstY = dy;    //??μ?Y×?±ê
    for (i = 0; i < Height; i++)
    {
        for (j = 0; j < Width; j++)
        {
            graph[i][j].x = i; //μ?í?×?±êX
            graph[i][j].y = j; //μ?í?×?±êY
            graph[i][j].value = map[i][j];
            graph[i][j].reachable = (graph[i][j].value == Reachable);    // ?úμ??éμ?′?D?
            graph[i][j].sur = 0; //áú?ó?úμ???êy
            if (!graph[i][j].reachable)
            {
                continue;
            }
            if (j > 0)
            {
                if (graph[i][j - 1].reachable)    // left?úμ??éò?μ?′?
                {
                    graph[i][j].sur |= West;
                    graph[i][j - 1].sur |= East;
                }
                if (i > 0)
                {
                    if (graph[i - 1][j - 1].reachable
                        && graph[i - 1][j].reachable
                        && graph[i][j - 1].reachable)    // up-left?úμ??éò?μ?′?
                    {
                        graph[i][j].sur |= North_West;
                        graph[i - 1][j - 1].sur |= South_East;
                    }
                }
            }
            if (i > 0)
            {
                if (graph[i - 1][j].reachable)    // up?úμ??éò?μ?′?
                {
                    graph[i][j].sur |= North;
                    graph[i - 1][j].sur |= South;
                }
                if (j < Width - 1)
                {
                    if (graph[i - 1][j + 1].reachable
                        && graph[i - 1][j].reachable
                        && map[i][j + 1] == Reachable) // up-right?úμ??éò?μ?′?
                    {
                        graph[i][j].sur |= North_East;
                        graph[i - 1][j + 1].sur |= South_West;
                    }
                }
            }
        }
    }
}
  
int bfs()
{
    int times = 0;
    int i, curX, curY, surX, surY;
    unsigned char f = 0, r = 1;
    Close *p;
    Close* q[MaxLength] = { &close[srcX][srcY] };
  
    initClose(close, srcX, srcY, dstX, dstY);
    close[srcX][srcY].vis = 1;
  
    while (r != f)
    {
        p = q[f];
        f = (f + 1) % MaxLength;
        curX = p->cur->x;
        curY = p->cur->y;
        for (i = 0; i < 8; i++)
        {
            if (! (p->cur->sur & (1 << i)))
            {
                continue;
            }
            surX = curX + dir[i].x;
            surY = curY + dir[i].y;
            if (! close[surX][surY].vis)
            {
                close[surX][surY].from = p;
                close[surX][surY].vis = 1;
                close[surX][surY].G = p->G + 1;
                q[r] = &close[surX][surY];
                r = (r + 1) % MaxLength;
            }
        }
        times++;
    }
    return times;
}
  
int astar()
{    // A*??·¨±éàú
    //int times = 0;
    int i, curX, curY, surX, surY;
    float surG;
    Open q; //Open±í
    Close *p;
  
    initOpen(&q);
    initClose(close, srcX, srcY, dstX, dstY);
    close[srcX][srcY].vis = 1;
    push(&q, close, srcX, srcY, 0);
  
    while (q.length)
    {    //times++;
        p = shift(&q);
        curX = p->cur->x;
        curY = p->cur->y;
        if (!p->H)
        {
            return Sequential;
        }
        for (i = 0; i < 8; i++)
        {
            if (! (p->cur->sur & (1 << i)))
            {
                continue;
            }
            surX = curX + dir[i].x;
            surY = curY + dir[i].y;
            if (!close[surX][surY].vis)
            {
                close[surX][surY].vis = 1;
                close[surX][surY].from = p;
                surG = p->G + sqrt((curX - surX) * (curX - surX) + (curY - surY) * (curY - surY));
                push(&q, close, surX, surY, surG);
            }
        }
    }
    //printf("times: %d\n", times);
    return NoSolution; //?T?á1?
}
  
const int map[Height][Width] = {
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
};
  
const char Symbol[5][3] = { "??", "¨?", "¨?", "??", "?ò" };
  
void printMap()
{
    int i, j;
    for (i = 0; i < Height; i++)
    {
        for (j = 0; j < Width; j++)
        {
            printf("%s", Symbol[graph[i][j].value]);
        }
        puts("");
    }
    puts("");
}
  
Close* getShortest()
{    // ??è?×??ì?·??
    int result = astar();
    Close *p, *t, *q = NULL;
    switch(result)
    {
    case Sequential:    //?3Dò×??ü
        p = &(close[dstX][dstY]);
        while (p)    //×a???·??
        {
            t = p->from;
            p->from = q;
            q = p;
            p = t;
        }
        close[srcX][srcY].from = q->from;
        return &(close[srcX][srcY]);
    case NoSolution:
        return NULL;
    }
    return NULL;
}
  
static Close *start;
static int shortestep;
int printShortest()
{
    Close *p;
    int step = 0;
  
    p = getShortest();
    start = p;
    if (!p)
    {
        return 0;
    }
    else
    {
        while (p->from)
        {
            graph[p->cur->x][p->cur->y].value = Pass;
            printf("￡¨%d￡?%d￡??ú\n", p->cur->x, p->cur->y);
            p = p->from;
            step++;
        }
        printf("￡¨%d￡?%d￡?\n", p->cur->x, p->cur->y);
        graph[srcX][srcY].value = Source;
        graph[dstX][dstY].value = Destination;
        return step;
    }
}
  
void clearMap()
{    // Clear Map Marks of Steps
    Close *p = start;
    while (p)
    {
        graph[p->cur->x][p->cur->y].value = Reachable;
        p = p->from;
    }
    graph[srcX][srcY].value = map[srcX][srcY];
    graph[dstX][dstY].value = map[dstX][dstY];
}
  
void printDepth()
{
    int i, j;
    for (i = 0; i < Height; i++)
    {
        for (j = 0; j < Width; j++)
        {
            if (map[i][j])
            {
                printf("%s ", Symbol[graph[i][j].value]);
            }
            else
            {
                printf("%2.0lf ", close[i][j].G);
            }
        }
        puts("");
    }
    puts("");
}
  
void printSur()
{
    int i, j;
    for (i = 0; i < Height; i++)
    {
        for (j = 0; j < Width; j++)
        {
            printf("%02x ", graph[i][j].sur);
        }
        puts("");
    }
    puts("");
}
  
void printH()
{
    int i, j;
    for (i = 0; i < Height; i++)
    {
        for (j = 0; j < Width; j++)
        {
            printf("%02d ", close[i][j].H);
        }
        puts("");
    }
    puts("");
}
  
int main(int argc, const char **argv)
{
    initGraph(map, 0, 0, 0, 0);
    printMap();
    puts("??ê?è??eê?×?±êó????1×?±ê￡o");
    while (scanf("%d %d %d %d", &srcX, &srcY, &dstX, &dstY) != EOF)
    {
        if (within(srcX, srcY) && within(dstX, dstY))
        {
            if (shortestep = printShortest())
            {
                printf("′ó￡¨%d￡?%d￡?μ?￡¨%d￡?%d￡?μ?×??ì2?êyê?: %d\n",
                    srcX, srcY, dstX, dstY, shortestep);
                printMap();
                clearMap();
                bfs();
                //printDepth();
                puts((shortestep == close[dstX][dstY].G) ? "?yè·" : "′í?ó");
                clearMap();
            }
            else
            {
                printf("′ó￡¨%d￡?%d￡?2??éμ?′?￡¨%d￡?%d￡?\n",
                    srcX, srcY, dstX, dstY);
            }
        }
        else
        {
            puts("ê?è?′í?ó￡?");
        }
        puts("??ê?è??eê?×?±êó????1×?±ê￡o");
    }
    return (0);
}