题解

1 条题解

  • 0
    @ 2017-08-20 20:58:37

    -----------------------------------------------AC code-----------------------------------------------

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<queue>
    #include<vector>
    
    #ifdef WIN32
    #   define outl "%I64d"
    #else
    #   define outl "%lld"
    #endif
    
    #define trans(x, y) ((x-1)*n+y)
    
    using namespace std;
    
    typedef long long LL;
    const int INF = 1<<30;
    const int MAXN = 55;
    int n, m, g[MAXN][MAXN], st, ed;
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    
    struct Edge{
        int nxt, to, dis;
    }edge[100010];
    
    int head[MAXN*MAXN], edge_num;
    bool con[MAXN*MAXN][MAXN*MAXN];
    void add_edge(int from, int to){
        edge[++edge_num].nxt = head[from];
        edge[edge_num].to = to;
        head[from] = edge_num;
        con[from][to] = 1;
    }
    
    bool vis[MAXN][MAXN];
    void dfs(int x, int y, int source, int f){
        vis[x][y] = 1;
        if(g[x][y] == 2){
            vis[x][y] = 0;
            return;
        }
        if(g[x][y] != 1){
            if(!con[source][trans(x, y)])   add_edge(source, trans(x, y));
            vis[x][y] = 0;
            return;
        }
        if(g[x][y] == 1){
            for(int i = 0; i < 8; i++){
                int tx = x + dx[i];
                int ty = y + dy[i];
                if(tx >= 1 && tx <= m && ty >= 1 && ty <= n && trans(tx, ty) != source && trans(tx, ty) != f && !vis[tx][ty])
                    dfs(tx, ty, source, trans(x, y));
            }
        }
        vis[x][y] = 0;
    }
    
    int dis[MAXN*MAXN];
    LL cnt[MAXN*MAXN];
    bool inq[MAXN*MAXN];
    void spfa(){
        for(int i = 1; i <= n*m; i++)   dis[i] = INF;
        queue<int> q;
        q.push(st);
        inq[st] = 1;
        dis[st] = 0;
        cnt[st] = 1;
        while(!q.empty()){
            int cur = q.front(); q.pop();
            inq[cur] = 0;
            for(int i = head[cur]; i; i = edge[i].nxt){
                if(dis[edge[i].to] > dis[cur] + 1){
                    dis[edge[i].to] = dis[cur] + 1;
                    cnt[edge[i].to] = cnt[cur];
                    if(!inq[edge[i].to]){
                        q.push(edge[i].to);
                        inq[edge[i].to] = 1;
                    }
                }
                else if(dis[edge[i].to] == dis[cur] + 1){
                    cnt[edge[i].to] += cnt[cur];
                    if(!inq[edge[i].to]){
                        q.push(edge[i].to);
                        inq[edge[i].to] = 1;
                    }
                }
            }
        }
    }
        
    int main(){
        scanf("%d%d", &m, &n);
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++){
                scanf("%d", &g[i][j]);
                if(g[i][j] == 3)    st = trans(i, j);
                if(g[i][j] == 4)    ed = trans(i, j);
            }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 0; k < 8; k++){
                    int tx = i + dx[k];
                    int ty = j + dy[k];
                    if(tx >= 1 && tx <= m && ty >= 1 && ty <= n){
                        if(g[tx][ty] != 1 && g[tx][ty] != 2 && !con[trans(i, j)][trans(tx, ty)])
                            add_edge(trans(i, j), trans(tx, ty));
                        if(g[tx][ty] == 1)  dfs(tx, ty, trans(i, j), trans(i, j));
                    }
                }
            }
        }
        spfa();
        if(dis[ed] == INF){
            printf("-1");
            return 0;
        }
        printf("%d\n"outl, dis[ed]-1, cnt[ed]);
        return 0;
    }
    
  • 1

信息

难度
(无)
分类
最短路图结构 | 搜索 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者