IDA* 题解

这题里IDA* 比 BFS 快，所以我们可以采用IDA* ，并且我们可以用一些高效剪枝：

1. 定义一个二维数组，记录到达此地点的最短路径，如果此时的cnt已经大于等于，直接剪枝
2. 用曼哈顿距离定义一个cmp函数，每次将d二维数组用cmp来sort排序，优先dfs
   代码如下：

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

int n,m,ax,ay,bx,by,ans=INT_MAX,sx,sy;
vector<vector<char>> a;
vector<vector<int>> mdfs;
int cfs(int x,int y){
    return abs(x-bx)+abs(y-by);
}
bool cmp(pair<int,int> a,pair<int,int> b){
    return cfs(sx+a.first,sy+a.second)<cfs(sx+b.first,sy+b.second);
}

void dfs(int x,int y,int cnt,int t){
    if(x<1 || x>n || y<1 || y>m || a[x][y]=='#' || cnt>=mdfs[x][y] || cnt+cfs(x,y)>t)return;
    mdfs[x][y]=cnt;
    sx=x,sy=y;
    if(x==bx&&y==by){
        ans=min(ans,cnt);
        return;
    }
    vector<pair<int,int>> d={{-1,0}, {1,0}, {0,-1}, {0,1}};
    sort(d.begin(),d.end(),cmp);
    for(int i=0;i<4;i++)dfs(x+d[i].first,y+d[i].second,cnt+1,t);
}

int main(){
    cin>>n>>m>>ax>>ay>>bx>>by;
    a.resize(n+1,vector<char>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    int t=cfs(ax,ay);
    while(ans==INT_MAX){
        mdfs.resize(n+1,vector<int>(m+1,INT_MAX));
        dfs(ax,ay,0,t);
        t++;
    }
    cout<<ans;
}