1 条题解

  • 0
    @ 2023-10-5 20:35:20
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define N 35
    #define INF 0x3f3f3f3f
    using namespace std;
    typedef long long ll;
    int n,m;
    int map[N][N];
    ll num[N][N];
    int f[N][N];
    int v[N][N];
    struct point
    {
        int x,y;
    }st,ed;
    bool canarrive[N][N][N][N];
    int xx[9]={0,-1,-2,-2,-1,1,2,2,1};
    int yy[9]={0,-2,-1,1,2,2,1,-1,-2};
    void floodfill(int x,int y)
    {
        memset(v,0,sizeof(v));
        queue<point>q;
        point tmp;
        tmp.x=x,tmp.y=y;
        q.push(tmp);
        while(!q.empty())
        {
            point u=q.front();
            q.pop();
            for(int i=1;i<=8;i++)
            {
                tmp.x=u.x+xx[i],tmp.y=u.y+yy[i];
                if(tmp.x<=0||tmp.y<=0||tmp.x>n||tmp.y>m||v[tmp.x][tmp.y])continue;
                if(!map[tmp.x][tmp.y]||(tmp.x==ed.x&&tmp.y==ed.y))
                {
                    canarrive[x][y][tmp.x][tmp.y]=1;
                }else if(map[tmp.x][tmp.y]==1)
                {
                    q.push(tmp);
                    v[tmp.x][tmp.y]=1;
                }
            }
        }
    }
    void bfs()
    {
        memset(v,0,sizeof(v));
        queue<point>q;
        q.push(st);
        v[st.x][st.y]=1;
        f[st.x][st.y]=0;
        num[st.x][st.y]=1;
        while(!q.empty())
        {
            point u=q.front();
            q.pop();
            v[u.x][u.y]=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(canarrive[u.x][u.y][i][j])
                    {
                        if(i==ed.x&&j==ed.y)
                        {
                            if(f[u.x][u.y]<f[i][j])
                            {
                                f[i][j]=f[u.x][u.y];
                                num[i][j]=num[u.x][u.y];
                            }else if(f[u.x][u.y]==f[i][j])
                            {
                                num[i][j]+=num[u.x][u.y];
                            }
                        }else
                        {
                            if(f[u.x][u.y]+1<f[i][j])
                            {
                                f[i][j]=f[u.x][u.y]+1;
                                num[i][j]=num[u.x][u.y];
                                if(!v[i][j])
                                {
                                    v[i][j]=1;
                                    point tmp;
                                    tmp.x=i,tmp.y=j;
                                    q.push(tmp);
                                }
                            }else if(f[u.x][u.y]+1==f[i][j])
                            {
                                num[i][j]+=num[u.x][u.y];
                                if(!v[i][j])
                                {
                                    v[i][j]=1;
                                    point tmp;
                                    tmp.x=i,tmp.y=j;
                                    q.push(tmp);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==3)st.x=i,st.y=j;
                else if(map[i][j]==4)ed.x=i,ed.y=j;
            }
        }
        floodfill(st.x,st.y);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(!map[i][j])floodfill(i,j);
            }
        }
        memset(f,0x3f,sizeof(f));
        bfs();
        if(f[ed.x][ed.y]==0x3f3f3f3f)printf("-1\n");
        else
        {   
            printf("%d\n",f[ed.x][ed.y]);
            printf("%lld\n",num[ed.x][ed.y]);
        }
        return 0;
    }
    
    
    • 1

    [Usaco2007 Feb]Lilypad Pond 荷叶池塘

    信息

    ID
    1698
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    3
    已通过
    3
    上传者