A* is better than native DFS

For some problems, the A* with good heuristic can be faster than the native DFS algorithm.

An example

D — Medicines on Grid

Solution

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
using PII = pair<int, int>;
vector<PII> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// this is optimized dfs solution with priority queue, it works. Essentially, it is an A* search algorithm
bool dfs(vector<string>&grid, vector<vector<int>>&medicine, vector<vector<int>>&life, PII end, int curr_life, int i, int j){
    priority_queue<pair<int, PII>> pq;
    pq.push({curr_life, {i, j}});
    while (!pq.empty()){
 auto [curr_life, pos] = pq.top();
 auto [ii, jj] = pos;
 pq.pop();
 if (end.first == ii && end.second == jj)return true;
 if (medicine[ii][jj] > curr_life){
     curr_life = medicine[ii][jj];
     medicine[ii][jj] = 0;
 }
 if (curr_life == 0)continue;
 if (curr_life <= life[ii][jj])continue;
 life[ii][jj] = curr_life;
 int r, c;
 for (auto [di, dj]: dirs){
     r = ii + di;
     c = jj + dj;
     if (r >= 0 && r < (int)grid.size() && c >= 0 && c < (int)grid[0].size() && grid[r][c] != '#' && curr_life >= 1 && life[r][c] <= curr_life - 1){
  pq.push({curr_life - 1, {r, c}});
     }
 }
    }
    return false;
}
/*
 * this is a native dfs solution, it works but will get TLE.
bool dfs1(vector<string>&grid, vector<vector<int>>&medicine, vector<vector<int>>&life, PII end, int curr_life, int i, int j){
    if (end.first == i && end.second == j)return true;
    if (medicine[i][j] > curr_life){
 curr_life = medicine[i][j];
 medicine[i][j] = 0;
    }
    if (curr_life == 0)return false;
    if (curr_life <= life[i][j])return false;
    life[i][j] = curr_life);
    int r, c;    
    for (auto [di, dj]: dirs){
 r = i +di;
 c = j + dj;
 if (r >= 0 && r < (int)grid.size() && c >= 0 && c < (int)grid[0].size() && grid[r][c] != '#' && curr_life >= 1 && life[r][c] <= curr_life - 1){
     if (dfs(grid, medicine, life, end, curr_life - 1, r, c))return true;
 }
    }
    return false;
}
 */


int main(){
    int N, M;
    cin >> N >> M;
    vector<string>grid(N);
    for (int i = 0; i < N; i++)
    {
 cin >> grid[i];
    }
    int Q;
    cin >> Q;
    vector<vector<int>> medicine(N, vector<int>(M, 0));
    int ii, jj, mm;
    for (int i = 0; i < Q; i++){
 cin >> ii >> jj >> mm;
 ii--; jj--;
 medicine[ii][jj] = mm;
    }
    PII begin, end;
    for (int i = 0; i < N; i++){
 for (int j = 0; j < M; j++){
     if (grid[i][j] == 'S'){begin = {i, j};}
     if (grid[i][j] == 'T'){end = {i, j};}
 }
    }
    auto [ii_, jj_] = begin;
    vector<vector<int>> life(N, vector<int>(M, 0));
    auto ret = dfs(grid, medicine, life, end, 0, ii_, jj_);
    if (ret)cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

The dfs1 is a native DFS solution, by using it the code will get TLE, however, if switch to dfs, which is essential an A* algorithm, the code can get AC.

Thanks for reading and I hope it is helpful!