Codeforces 677D Vanya and Treasure 暴力+BFS


链接

Codeforces 677D Vanya and Treasure

题意

n*m中有p个type,经过了任意一个 type=i 的各自才能打开 type=i+1 的钥匙,最初有type=1的钥匙, 问拿到type=p的钥匙最少需要走多少步

思路

第一想法就是按type来递推, 将type相同的存到一起,dp[i][j]=min(dp[i][j], dp[k][l]+distance([i][j], [k][l])),其中 a[i][j] = a[k][l]+1. 但这样type相同的个数较多时就超时了,所以根据type的个数,较多时使用BFS就可以了。 我没有仔细研究时间复杂度就过了,官方题解好像有均摊复杂度的证明。

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <string>

#define LL long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define MOD 1000000007
using namespace std;

struct POS{
    int x, y;
    POS(int x = 0, int y = 0) :x(x), y(y){};
};
vector<POS> s[90005];
int a[305][305];
int d[305][305];
bool vis[305][305];
int dp[305][305];
const int step[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };
int get_distance(POS &a, POS &b){
    return abs(a.x - b.x) + abs(a.y - b.y);
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int n, m, p;
    while (~scanf("%d%d%d", &n, &m, &p)){
        int x;
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= m; ++j){
                scanf("%d", &a[i][j]);
                s[a[i][j]].push_back(POS(i, j));
            }
        }
        memset(dp, INF, sizeof(dp));
        for (int i = 0; i < s[1].size(); ++i){
            dp[s[1][i].x][s[1][i].y] = s[1][i].x + s[1][i].y - 2;
        }
        for (int i = 2; i <= p; ++i){
            if (s[i].size() * s[i - 1].size() < n * m){
                for (int j = 0; j < s[i].size(); ++j){
                    POS J = s[i][j];
                    for (int k = 0; k < s[i - 1].size(); ++k){
                        POS K = s[i - 1][k];
                        dp[J.x][J.y] = min(dp[K.x][K.y] + get_distance(J, K), dp[J.x][J.y]);
                    }
                }
            }
            else{
                memset(d, INF, sizeof(d));
                memset(vis, 0, sizeof(vis));
                queue<POS> Q;
                for (int j = 0; j < s[i - 1].size(); ++j){
                    POS J = s[i - 1][j];
                    Q.push(J);
                    vis[J.x][J.y] = true;
                    d[J.x][J.y] = dp[J.x][J.y];
                }
                while (!Q.empty()){
                    POS u = Q.front();
                    Q.pop();
                    vis[u.x][u.y] = false;
                    for (int j = 0; j < 4; ++j){
                        int x = u.x + step[j][0];
                        int y = u.y + step[j][1];
                        if (a[u.x][u.y] == i) dp[u.x][u.y] = min(dp[u.x][u.y], d[u.x][u.y]);
                        if (x < 1 || x >  n || y < 1 || y > m) continue;
                        if (d[x][y] > d[u.x][u.y] + 1){
                            d[x][y] = d[u.x][u.y] + 1;
                            if (!vis[x][y]){
                                vis[x][y] = true;
                                if (a[x][y] == i){
                                    dp[x][y] = min(dp[x][y], d[x][y]);
                                }
                                Q.push(POS(x, y));
                            }
                        }
                    }
                }
            }
        }
        POS K = s[p][0];
        cout << dp[K.x][K.y] << endl;
    }
}
智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告