礼物（BFS）

礼物

时间限制: 1 Sec 内存限制: 64 MB
提交: 39 解决: 4
[提交][状态][讨论版]

题目描述

　
　给出一个n行m列的点阵，“．”表示可通行格子，“#”表示不可通行格子，“K”表示国王的初始位置，“Q”表示王后的位置，“G”表示该格子有一个礼
物。注意：国王、王后、礼物所在的格子可以认为是可通行格子。国王从开始位置出发，国王从当前格子可以走到上、下、左、右四个相邻格子，当然前提是可通行
格子。国王从当前格子走到相邻格子的时间是变化的，这取决于国王手头上收集到的礼物的数量，假如当前国王手头上有y个礼物，那么他从当前格子移动到相邻格
子的所用时间是y+l秒。一旦国王进入某个有礼物的格子，他可以选择取该格子的礼物，也可以选择不取该格子的礼物。取礼物这个动作可以认为是瞬间完成的，
不需要时间。国王想收集到尽量多的礼物送给王后，但是他到达王后所在的格子不能超过T秒，王后不想等太长时间。注意：国王在收集礼物的途中可能多次走到相
同的格子。

输入

　第1行：三个整数n、m、T。 1≤n，m≤50，1≤T≤109。
　接下来是n行m列的点阵，‘G’的数量不超过16。只有一个国王，一个王后。

输出

一个整数，国王在规定时间内，最多可以收集到多少个礼物送给王后？

样例输入

5 7 50

#....G#

###G###

#K...Q#

###.###

#G..GG#

样例输出

4
【分析】威哥写的，表示并不懂，立个flag，日后再学，已经看晕了。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#include<functional>

#define mod 1000000007

#define inf 0x3f3f3f3f

#define pi acos(-1.0)

using namespace std;

typedef long long ll;

const int N = (<<)+;

const int INF = 0x3f3f3f3f;

char s[][];

int n,m,T;

struct Node {

    int x,y;

    Node(int a=,int b=) {

        x=a;

        y=b;

    }

} st,ed;

vector<Node>g;

int d[][],dis[][],f[N][];

int dx[]= {,,-,};

int dy[]= {-,,,};

void bfs(int pos) {

    queue<Node>q;

    memset(dis,INF,sizeof(dis));

    dis[g[pos].x][g[pos].y]=;

    q.push(g[pos]);

    while(!q.empty()) {

        Node u=q.front();

        q.pop();

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

            int x=u.x+dx[i],y=u.y+dy[i];

            if(x<||x>n||y<||y>m||s[x][y]=='#')continue;

            if(dis[x][y]==INF) {

                dis[x][y]=dis[u.x][u.y]+;

                q.push(Node(x,y));

            }

        }

    }

    for(int i=; i<g.size(); ++i)if(i!=pos) {

            d[pos][i]=dis[g[i].x][g[i].y];

        }

}

int main() {

    scanf("%d%d%d",&n,&m,&T);

    for(int i=; i<=n; ++i)scanf("%s",s[i]+);

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

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

            if(s[i][j]=='K')st=Node(i,j);

            else if(s[i][j]=='Q')ed=Node(i,j);

            else if(s[i][j]=='G')g.push_back(Node(i,j));

        }

    }

    g.push_back(st);

    g.push_back(ed);

    memset(d,INF,sizeof(d));

    memset(f,INF,sizeof(f));

    for(int i=; i<g.size()-; ++i)bfs(i);

    int ss=g.size()-,tt=g.size()-,tot=(<<(g.size()-));

    for(int i=; i<g.size()-; ++i) {

        f[<<i][i]=d[ss][i];

    }

    for(int i=; i<tot; ++i) {

        for(int j=; j<g.size()-; ++j) {

            if(!(i&(<<j))||f[i][j]>=INF)continue;

            for(int k=; k<g.size()-; ++k) {

                if((i&(<<k))||d[j][k]>=INF)continue;

                f[i|(<<k)][k]=min(f[i][j]+(__builtin_popcount(i)+)*d[j][k],f[i|(<<k)][k]);

            }

        }

    }

    int ret=;

    for(int i=; i<tot; ++i) {

        for(int j=; j<g.size()-; ++j) {

            if(f[i][j]!=INF||d[j][tt]!=INF) {

                int tmp=f[i][j]+(__builtin_popcount(i)+)*d[j][tt];

                if(tmp<=T) ret=max(ret,__builtin_popcount(i));

            }

        }

    }

    printf("%d\n",ret);

    return ;

}

巴特西

礼物（BFS）

礼物

题目描述

输入

输出

样例输入

样例输出

最新文章

热门文章