首页 > 搜索 > BFS搜索 > HDU 4536-XCOM Enemy Unknown-BFS-[解题报告]HOJ
2015
07-17

HDU 4536-XCOM Enemy Unknown-BFS-[解题报告]HOJ

XCOM Enemy Unknown

问题描述 :

XCOM-Enemy Unknown是一款很好玩很经典的策略游戏.
在游戏中,由于未知的敌人–外星人入侵,你团结了世界各大国家进行抵抗.

吉哥系列故事――礼尚往来

随着游戏进展,会有很多的外星人进攻事件.每次进攻外星人会选择3个国家攻击,作为联盟的指挥者,你要安排有限的联盟军去支援其中一个国家,抵抗进攻这个国家的外星人.

吉哥系列故事――礼尚往来

战斗胜利之后这个被支援的国家恐慌值就会-2点(恐慌值最少减为1),而其他两个未被支援的国家恐慌值就会+2点,同时和这两个国家在相同大洲的其他国家恐慌值也会+1点.
当一个国家的恐慌值超过5点,这个国家就会对联盟失去信心从而退出联盟.
现在给你外星人将会进攻的地点,问你最多能在不失去任何一个国家信任的情况下抵挡多少次外星人的进攻.

输入:

第一行有一个整数T代表接下来有T组数据
每组数据第一行是三个整数,n,m,k分别代表联盟国家的个数,大洲的个数,外星人的进攻次数.
第二行是n个数字代表各个国家所属的大洲(大洲序号从0到m-1)
第三行是n个数字代表各个国家初始的恐慌值
接下去k行代表外星人进攻
每行有三个数字,表示该次外星人进攻的国家(国家序号从0到n-1)

[Technical Specification]
0<T<=100
8<n<=16
2<m<=5
0<k<=100
0<初始恐慌值<=5
每个州至少有三个国家
每次外星人进攻一定发生在不同州的三个国家

输出:

第一行有一个整数T代表接下来有T组数据
每组数据第一行是三个整数,n,m,k分别代表联盟国家的个数,大洲的个数,外星人的进攻次数.
第二行是n个数字代表各个国家所属的大洲(大洲序号从0到m-1)
第三行是n个数字代表各个国家初始的恐慌值
接下去k行代表外星人进攻
每行有三个数字,表示该次外星人进攻的国家(国家序号从0到n-1)

[Technical Specification]
0<T<=100
8<n<=16
2<m<=5
0<k<=100
0<初始恐慌值<=5
每个州至少有三个国家
每次外星人进攻一定发生在不同州的三个国家

样例输入:

1
9 3 2
0 0 0 1 1 1 2 2 2
3 3 3 3 3 3 3 3 3
0 3 6
0 3 6

样例输出:

Case #1: 1

Hint
第一次如果选择了0,那么3和6的恐慌值就会增加到5,第二次不管怎么选择,3和6总会有一个超过5.

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4536

爆搜。

#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <stack>
#include <deque>
using namespace std;
typedef  long long  LL;
#define eps 10e-9
#define inf 0x3f3f3f3f
const int maxn = 1000+100;
const int mod  = 1000000000+7;
int n,m,k;
struct node{
      int b[18];
      int step;
}s_pos;
vector<int > v[10];
int c[maxn];
int a1[maxn],a2[maxn],a3[maxn];
int ans,f;
void solve(node &now,int c1,int c2,int c3){
           now.b[c1]-=2;   if(now.b[c1]<1) now.b[c1]=1;
           now.b[c2]+=1;   if(now.b[c2]>5) {
               f=1; return ;
           }
           now.b[c3]+=1;   if(now.b[c3]>5){
                f=1; return ;
           }
           for(int  i=0;i<v[ c[c2] ].size();i++){
               now.b[ v[ c[c2] ][i] ]++;
               if( now.b[ v[ c[c2] ][i] ]>5 ) {
                   f=1;return;
               }
           }
           for(int  i=0;i<v[ c[c3] ].size();i++){
               now.b[ v[ c[c3] ][i] ]++;
            if( now.b[ v[ c[c3] ][i] ]>5 ){
                 f=1; return;
            }
           }

}
void bfs(){
     queue<node > q;
     q.push(s_pos);
     while(!q.empty()){
           node now = q.front(),next; q.pop();
           if(now.step-1>ans) ans=now.step-1;

           int key=now.step;
           if(now.step>k){
               ans=k;
               return ;
           }
           now.step++;

           f=0; next=now;
           solve(next,a1[key],a2[key],a3[key]);
           if(!f) q.push(next);

           f=0;next=now;
           solve(next,a2[key],a1[key],a3[key]);
           if(!f) q.push(next);

           f=0; next=now;
           solve(next,a3[key],a2[key],a1[key]);
           if(!f) q.push(next);

     }
}
int main(){
    int T,h; scanf("%d",&T);
    int ca=1;
    while(T--){
        scanf("%d %d %d",&n,&m,&k);
        for(int i=0;i<=6;i++) v[i].clear();
        for(int i=0;i<n;i++) {
            scanf("%d",&h);
            c[i]=h;
            v[h].push_back(i);
        }
        for(int i=0;i<n;i++) scanf("%d",&s_pos.b[i]);
        s_pos.step=1;
        for(int i=1;i<=k;i++) scanf("%d %d %d",&a1[i],&a2[i],&a3[i]);
        ans=0;
        bfs();
        printf("Case #%d: %d\n",ca++,ans);
    }

    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/w00w12l/article/details/8741144


,