【NOIP模拟赛】chess 建图+spfa统计方案数

似乎弗洛伊德和迪杰斯特拉都干不了统计方案数，spfa的话就是不断入队就好。

#include <cstdio>

#include <cstring>

#include <queue>

#define get_hash(a,b) (a-1)*m+b

const int N=;

const int Inf=0x3f3f3f3f;

int t1[]={-,-,-,-,,,,},t2[]={-,-,,,,,-,-};

int f[N*N],dis[N*N],n,s[N][N],m,hash[N][N],S,E,all;

bool in[N*N],v[N][N],is[N*N],edge[N*N][N*N];

inline bool ok(int x,int y){

    return x>&&x<=n&&y>&&y<=m&&s[x][y]!=;

}

struct V{

    int to,next;

}c[N*N*N*N];

int head[N*N],t;

std::queue<int>q;

inline void add(int x,int y){

    c[++t].to=y,c[t].next=head[x],head[x]=t;

}

void dfs(int x,int y){

    if(v[x][y])return;

    v[x][y]=;

    for(int i=,p1,p2;i<;i++){

        p1=x+t1[i],p2=y+t2[i];

        if(ok(p1,p2)==false)continue;

        if(s[p1][p2]==)dfs(p1,p2);

        else is[hash[p1][p2]]=true;

    }

}

void read_build(){

    scanf("%d%d",&n,&m),all=n*m;

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++){

            scanf("%d",&s[i][j]),hash[i][j]=get_hash(i,j);

            if(s[i][j]==)S=hash[i][j];

            if(s[i][j]==)E=hash[i][j];

        }

    for(int i=,p1,p2;i<=n;i++)

        for(int j=;j<=m;j++)

            if(s[i][j]!=&&s[i][j]!=)

                if(s[i][j]==){

                    memset(is,,sizeof(is)),dfs(i,j);

                    for(int x=;x<=all;x++)

                        if(is[x]&&x!=E)

                            for(int y=;y<=all;y++)

                                if(x!=y&&is[y])

                                    edge[x][y]=true;

                }

                else

                    for(int k=;k<;k++){

                        p1=t1[k]+i,p2=t2[k]+j;

                        if(ok(p1,p2)&&s[p1][p2]!=)

                            add(hash[i][j],hash[p1][p2]);

                    }

    for(int i=;i<=all;i++)

        for(int j=;j<=all;j++)

            if(i!=j&&edge[i][j])

                add(i,j);

}

void spfa_print(){

    q.push(S),memset(dis,0x3f,sizeof(dis)),dis[S]=,f[S]=,in[S]=true;

    while(!q.empty()){

        int x=q.front();q.pop(),in[x]=false;

        for(int i=head[x];i;i=c[i].next)

            if(dis[x]+<dis[c[i].to]){

                dis[c[i].to]=dis[x]+,f[c[i].to]=f[x];

                if(in[c[i].to]==false)q.push(c[i].to),in[c[i].to]=true;

            }

            else if(dis[x]+==dis[c[i].to]){

                f[c[i].to]+=f[x];

                if(in[c[i].to]==false)q.push(c[i].to),in[c[i].to]=true;

            }

    }

    if(f[E]==)printf("-1");

    else printf("%d\n%d",dis[E]-,f[E]);

}

int main(){

    read_build(),spfa_print();

    return ;

}