A* Search Algorithm

A* (A-star) is a best-first graph search algorithm that finds the shortest path between a start node and a goal node. It uses a heuristic function h(n) to estimate the cost from any node n to the goal, guiding the search efficiently. The total estimated cost is f(n) = g(n) + h(n), where g(n) is the cost from the start to n.

Algorithm Details

1. Initialize the open set (priority queue) with the start node, where g(start)=0 and f(start)=h(start).
2. While the open set is not empty:
   • Pop node u with lowest f(u) from the queue.
   • If u is the goal, reconstruct and return the path.
   • For each neighbor v of u:
   • Compute tentative cost g_temp = g(u) + cost(u, v).
   • If g_temp < g(v), update g(v)=g_temp, f(v)=g(v)+h(v), and set parent[v]=u. Push or update v in the open set.
3. If the open set empties without reaching the goal, no path exists.

Complexity

• Time: In the worst case O(E + V log V) when using a binary heap. Without heuristic (i.e., h=0), it reduces to Dijkstra's algorithm.
• Memory: O(V) to store the open and closed sets as well as cost arrays.

Easy-Level Problems

1. Grid Path (AtCoder ABC184D)

Problem: Given an H×W grid with free cells . and obstacles #, find the minimum number of steps from start (sx, sy) to goal (gx, gy). You can move in four directions.

Solution Explanation: We model the grid as a graph where each cell is a node and edges connect adjacent free cells with cost 1. Using A*, we take Manhattan distance as an admissible heuristic (h(n)=|x-gx|+|y-gy|), which never overestimates the true remaining cost. Thus A* will find the optimal path, exploring fewer nodes than BFS when obstacles exist.

#include <bits/stdc++.h>
using namespace std;
typedef pair pii;

struct Node {
    int x, y;
    int g, f;
};

struct Compare {
    bool operator()(Node const &a, Node const &b) const {
        return a.f > b.f;
    }
};

int main() {
    int H, W;
    cin >> H >> W;

    vector grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }

    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    sx--; sy--; gx--; gy--;

    auto heuristic = [&](int x, int y) {
        return abs(x - gx) + abs(y - gy);
    };

    vector> g(H, vector(W, INT_MAX));
    priority_queue, Compare> openSet;

    g[sx][sy] = 0;
    openSet.push({sx, sy, 0, heuristic(sx, sy)});

    int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    while (!openSet.empty()) {
        Node cur = openSet.top();
        openSet.pop();

        if (cur.x == gx && cur.y == gy) {
            cout << cur.g;
            return 0;
        }

        if (cur.g > g[cur.x][cur.y]) continue;

        for (auto &d : dirs) {
            int nx = cur.x + d[0];
            int ny = cur.y + d[1];

            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (grid[nx][ny] == '#') continue;

            int ng = cur.g + 1;
            if (ng < g[nx][ny]) {
                g[nx][ny] = ng;
                openSet.push({nx, ny, ng, ng + heuristic(nx, ny)});
            }
        }
    }

    cout << -1;
    return 0;
}

2. Knight Moves (AtCoder ARC010B)

Problem: On an N×N chessboard, find the minimum number of knight moves from (sx, sy) to (gx, gy).

Solution Explanation: We represent each board position as a node, edges connect valid knight moves with cost 1. An admissible heuristic for knight distance is h(dx,dy)=max((|dx|+1)/2,(|dx|+|dy|+2)/3), guaranteeing h never overestimates. A* guided by this heuristic efficiently finds the shortest path.

#include <bits/stdc++.h>
using namespace std;

int heuristic(int dx, int dy) {
    dx = abs(dx);
    dy = abs(dy);
    return max((dx + 1) / 2, (dx + dy + 2) / 3);
}

struct Node {
    int x, y;
    int g, f;
};

struct Compare {
    bool operator()(Node const &a, Node const &b) const {
        return a.f > b.f;
    }
};

int main() {
    int N;
    cin >> N;

    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    sx--; sy--; gx--; gy--;

    vector> g(N, vector(N, INT_MAX));
    priority_queue, Compare> openSet;

    auto pushNode = [&](int x, int y, int cost) {
        int h = heuristic(gx - x, gy - y);
        g[x][y] = cost;
        openSet.push({x, y, cost, cost + h});
    };

    pushNode(sx, sy, 0);

    int dx[8] = {2, 2, -2, -2, 1, 1, -1, -1};
    int dy[8] = {1, -1, 1, -1, 2, -2, 2, -2};

    while (!openSet.empty()) {
        Node cur = openSet.top();
        openSet.pop();

        if (cur.x == gx && cur.y == gy) {
            cout << cur.g;
            return 0;
        }

        if (cur.g > g[cur.x][cur.y]) continue;

        for (int i = 0; i < 8; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

            int ng = cur.g + 1;
            if (ng < g[nx][ny]) {
                pushNode(nx, ny, ng);
            }
        }
    }

    cout << -1;
    return 0;
}

Intermediate-Level Problems

3. Sliding Puzzle (AtCoder ABC263E)

Problem: Solve a 3×3 sliding puzzle to reach the goal state 123456780.

Solution Explanation: We treat each permutation of tiles as a node, and moves as edges of cost 1. We use the sum of Manhattan distances of each tile from its goal position as an admissible heuristic, ensuring optimality of A*. This dramatically reduces states explored versus uninformed BFS.

#include <bits/stdc++.h>
using namespace std;
using State = string;

int heuristic(const State &s) {
    int res = 0;
    for (int i = 0; i < 9; i++) {
        if (s[i] != '0') {
            int d = s[i] - '1';
            res += abs(i / 3 - d / 3) + abs(i % 3 - d % 3);
        }
    }
    return res;
}

struct Node {
    State s;
    int g, f;
};

struct Compare {
    bool operator()(Node const &a, Node const &b) const {
        return a.f > b.f;
    }
};

int main() {
    State start;
    for (int i = 0; i < 9; i++) {
        char c; cin >> c;
        start += c;
    }
    State goal = "123456780";

    priority_queue, Compare> openSet;
    unordered_map dist;

    dist[start] = 0;
    openSet.push({start, 0, heuristic(start)});

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    while (!openSet.empty()) {
        Node cur = openSet.top();
        openSet.pop();

        if (cur.s == goal) {
            cout << cur.g;
            return 0;
        }

        if (cur.g > dist[cur.s]) continue;

        int z = cur.s.find('0');
        int x = z / 3;
        int y = z % 3;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;

            State next = cur.s;
            swap(next[z], next[nx * 3 + ny]);

            int ng = cur.g + 1;
            if (!dist.count(next) || ng < dist[next]) {
                dist[next] = ng;
                openSet.push({next, ng, ng + heuristic(next)});
            }
        }
    }

    cout << -1;
    return 0;
}

4. Robot on Ice (Codeforces 239B)

Problem: A robot slides on ice: once it moves in a direction, it continues until hitting an obstacle or boundary. Find the minimum number of slides from start to goal.

Solution Explanation: We create nodes for each position; edges connect to landing positions after a slide with cost 1. As heuristic, we use Euclidean distance divided by maximum grid dimension, which underestimates slide count, making it admissible. A* thus quickly focuses search toward the goal.

#include <bits/stdc++.h>
using namespace std;
typedef pair pii;

struct Node {
    int x, y;
    int g, f;
};

struct Compare {
    bool operator()(Node const &a, Node const &b) const {
        return a.f > b.f;
    }
};

int main() {
    int H, W;
    cin >> H >> W;
    vector grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }

    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    sx--; sy--; gx--; gy--;

    auto heuristic = [&](int x, int y) {
        double d = hypot(x - gx, y - gy);
        return (int)ceil(d / max(H, W));
    };

    priority_queue, Compare> openSet;
    vector> dist(H, vector(W, INT_MAX));

    auto pushNode = [&](int x, int y, int cost) {
        dist[x][y] = cost;
        openSet.push({x, y, cost, cost + heuristic(x, y)});
    };

    pushNode(sx, sy, 0);
    int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    while (!openSet.empty()) {
        Node cur = openSet.top();
        openSet.pop();

        if (cur.x == gx && cur.y == gy) {
            cout << cur.g;
            return 0;
        }

        if (cur.g > dist[cur.x][cur.y]) continue;

        for (auto &d : dirs) {
            int nx = cur.x;
            int ny = cur.y;
            while (true) {
                int tx = nx + d[0];
                int ty = ny + d[1];
                if (tx < 0 || tx >= H || ty < 0 || ty >= W || grid[tx][ty] == '#') break;
                nx = tx; ny = ty;
            }
            if (nx == cur.x && ny == cur.y) continue;
            int ng = cur.g + 1;
            if (ng < dist[nx][ny]) {
                pushNode(nx, ny, ng);
            }
        }
    }

    cout << -1;
    return 0;
}

Hard-Level Problem

Naval Warfare (AtCoder AGC029D)

Problem: Given a sea grid with ships (~ cost 2) and open water (cost 1), find the minimum fuel path from start to goal using A*.

Solution Explanation: We define node costs by terrain: open water =1, ships =2. Edges connect adjacent cells. Heuristic is Manhattan distance, which never overestimates the remaining fuel. A* guided by this heuristic finds the minimum-fuel path efficiently.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    int x, y;
    ll g, f;
};

struct Compare {
    bool operator()(Node const &a, Node const &b) const {
        return a.f > b.f;
    }
};

int main() {
    int H, W;
    cin >> H >> W;
    vector grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }

    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    sx--; sy--; gx--; gy--;

    auto costAt = [&](int x, int y) -> ll {
        return (grid[x][y] == '~') ? 2LL : 1LL;
    };

    auto heuristic = [&](int x, int y) {
        return llabs(x - gx) + llabs(y - gy);
    };

    priority_queue, Compare> openSet;
    vector> dist(H, vector(W, LLONG_MAX));

    auto pushNode = [&](int x, int y, ll cost) {
        dist[x][y] = cost;
        openSet.push({x, y, cost, cost + heuristic(x, y)});
    };

    pushNode(sx, sy, 0);
    int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    while (!openSet.empty()) {
        Node cur = openSet.top();
        openSet.pop();

        if (cur.x == gx && cur.y == gy) {
            cout << cur.g;
            return 0;
        }

        if (cur.g > dist[cur.x][cur.y]) continue;

        for (auto &d : dirs) {
            int nx = cur.x + d[0];
            int ny = cur.y + d[1];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;

            ll ng = cur.g + costAt(nx, ny);
            if (ng < dist[nx][ny]) {
                pushNode(nx, ny, ng);
            }
        }
    }

    cout << -1;
    return 0;
}