hdoj 1428 漫步校园【BFS+DFS】

朴灿烈づ我的快乐病毒、 2022-08-12 09:58 48阅读 0赞

题目：[hdoj 1428 漫步校园 ][hdoj 1428 _]

分析：题意还是有必要说的，他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近，注意这句话，可见先让你求每个点到机房（n,n）点的最短路。当然这里用BFS比较好，注意要用优先队列.。接着这句话告诉你，每次选择走的时候可以有多种选择，只要满足上面每一步都比当前这一步更近，即dis【child】 < dis【father】，然后求到终点有多少条。（注意不是求最短路有多少种走法），这一步可以用记忆话深搜，用dp【i】【j】表示从当前点到终点有多少种，然后枚举深搜。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <queue>
    typedef long long ll;
    using namespace std;
    const int N = 55;
    int mp[N][N],dis[N][N];         //dis[i][j] 表示从n，n到i，j的最短路
    ll dp[N][N];
    int n;
    int dx[5]={1,-1,0,0};
    int dy[5]={0,0,1,-1};
    struct Node
    {
        int x,y,step;
        bool operator < (const Node &a) const
        {
            return a.step<step;   //首先出队的是最小的
        }
    };
    void bfs(int x,int y)
    {
        memset(dis,0,sizeof(dis));
        dis[x][y]=mp[x][y];
        priority_queue<Node> q;
        Node st,tmp;
        st.x=x,st.y=y,st.step=mp[x][y];
        q.push(st);mp[x][y]=-1;
        while(!q.empty())
        {
            st=q.top();q.pop();
            for(int i=0;i<4;i++)
            {
                tmp.x=st.x+dx[i];
                tmp.y=st.y+dy[i];
                tmp.step=st.step+mp[tmp.x][tmp.y];
                if(tmp.x>0 && tmp.x<=n && tmp.y>0 && tmp.y<=n && mp[tmp.x][tmp.y]!=-1)
                {
                    mp[tmp.x][tmp.y]=-1;
                    dis[tmp.x][tmp.y]=tmp.step;
                    q.push(tmp);
                }
            }
        }
    }
    ll dfs(int x,int y)
    {
        if(dp[x][y])
            return dp[x][y];
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>0 && xx<=n && yy>0 && yy<=n && dis[x][y]>dis[xx][yy])
                dp[x][y]+=dfs(xx,yy);
        }
        return dp[x][y];
    }
    int main()
    {
        while(~scanf("%d",&n))
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    scanf("%d",&mp[i][j]);
            bfs(n,n);
            memset(dp,0,sizeof(dp));
            dp[n][n]=1;
            printf("%I64d\n",dfs(1,1));
        }
        return 0;
    }

[hdoj 1428 _]: http://acm.hdu.edu.cn/showproblem.php?pid=1428