题意

有一个\(m*n\)的棋盘\((n,m\leq 50)\)，每个各自上有数字，一个马从起始位置出发跳向目标位置，走到0号格子会花费1代价，走到1号格子或者目标位置不花费代价，2号格子不能走，求\(S\)到\(T\)的最小代价及方案数（注意：两种方案不同当且仅当路径上的至少有一个不同的0号格子）

思路

下面的论述都不考虑2号格子

对于最小代价，很容易想到建图跑最短路：对于每个点向八个方向连边，如果是0号边权为1,1号边权为0，跑一遍dijkstra即可

对于方案数，如果两种方案不同的条件换成“两条路径上有一个点不同即可”且所有边权为1，这道题就是

然而两条路径不同只取决于0号格子，也就是说，从一个0号格子到另外一个0号格子，不需要管中间怎么走，也就是说其实1号格子并没有任何作用，如果两个0号点之间全是1号点，我们可以跳过这些1号点使得0号点直接相连（当然如果两个0号点之间还有0号点就不用管了）

所以，从每一个0号点出发（起点终点也要算0号点），dfs一遍找出所有的中间只经过1号格子即可到达的0号点，两者直接连边，用vis标记使得一个点在一次dfs中只出现一次，避免重边或者反复横跳

这样做之后，整张图边权全为1且只剩下0号格子连有边，当作最短路计数做即可，注意由于目标格子不要代价，最终的最短路长度要-1（这样做就已经可以求出最小代价了，可以不用特意跑一次dijkstra）

Code：

#include
    
     #define N 2605using namespace std;typedef long long ll;int n,m,S,T;int a[55][55];int dis[N],kkk;int dox[10]={-1,-2,-2,-1,1,2,2,1},doy[10]={-2,-1,1,2,2,1,-1,-2};bool vis[N];vector
     
       son[N];ll ans[N];struct Edge{    int next,to,dis;}edge[N<<4];int head[N],cnt=1;void add_edge(int from,int to,int dis){    edge[++cnt].next=head[from];    edge[cnt].to=to;    edge[cnt].dis=dis;    head[from]=cnt;}template 
      
       void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}int get_id(int x,int y) {    if(x<1||x>n||y<1||y>m) return -1;    return (x-1)*50+y;}void dfs(int root,int rt){    vis[rt]=1;    if(rt==S&&root!=rt) return;    if(a[(rt-1)/50+1][(rt-1)%50+1]%4==0&&rt!=root) {son[root].push_back(rt);return;}        for(int i=head[rt];i;i=edge[i].next)    {        int v=edge[i].to;        if(!vis[v]) dfs(root,v);    }}int main(){    freopen("chess.in","r",stdin);    freopen("chess.out","w",stdout);    read(n);read(m);    for(int i=1;i<=n;++i)    {        for(int j=1;j<=m;++j)        {            read(a[i][j]);            if(a[i][j]==3) S=get_id(i,j);            if(a[i][j]==4) T=get_id(i,j);        }    }    for(int i=1;i<=n;++i)//建图     {        for(int j=1;j<=m;++j)        {            if(a[i][j]==2) continue;//可有可无             int now=get_id(i,j);            for(int k=0;k<8;++k)            {                int dx=i+dox[k],dy=j+doy[k];                int v=get_id(dx,dy);                if(v==-1||a[dx][dy]==2) continue;//出界或者踩到友军                 if(a[dx][dy]==0||a[dx][dy]==3) add_edge(now,v,1);                else add_edge(now,v,0);            }        }    }    for(int i=1;i<=n;++i)    for(int j=1;j<=m;++j)    {        if(a[i][j]==0||a[i][j]==3)         {            memset(vis,0,sizeof(vis));            dfs(get_id(i,j),get_id(i,j));        }    }    memset(dis,-1,sizeof(dis));    queue
       
         q;    ans[S]=1; q.push(S); dis[S]=0;    while(!q.empty())    {        int u=q.front(); q.pop();        for(int i=0;i<(int)son[u].size();++i)        {            int v=son[u][i];            if(dis[v]==-1)            {                if(v!=T) dis[v]=dis[u]+1,q.push(v);//此处也可以不特判，最后dis[T]-1即可                else dis[v]=dis[u];            }            if(dis[v]==dis[u]+1||(dis[v]==dis[u]&&v==T)) ans[v]+=ans[u];        }    }    if(dis[T]==-1) cout<<-1<