首页 > ACM题库 > HDU-杭电 > HDU 3958-Tower Defence-动态规划-[解题报告]HOJ
2015
04-14

HDU 3958-Tower Defence-动态规划-[解题报告]HOJ

Tower Defence

问题描述 :

Tower Defence is a popular classic game. During the game, there will appear some monsters at the entry and each will find a shortest path to the exit. Your task is puting some warriors on the map to kill the monsters before they reach exit.
Street Fighter

You could put warrior(infinite) on the map to change the pathes of monsters. Of course, the longer the path is, the more advantageous to you.
Now, giving you the information of the map, how do you put the warriors to make the monsters move on the longest path?
The meaning of each character in the map:
‘S’ represents the entry of the map, one and only one;
‘T’ represents the exit of the map, one and only one;
‘.’ represents the grid that monster could move on;
‘B’ represents the barrier that monster couldn’t move on;
‘W’ represents the warrior that you put.(could only put on ‘.’)

输入:

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains two integers N, M (3<=N<=20 , 3<=M<=9)
Then N lines follow, each line contains M chars represent the map, include ‘S’,'T’,’.’,'B’.
I promise there must be at least one way from entry to exit.

输出:

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains two integers N, M (3<=N<=20 , 3<=M<=9)
Then N lines follow, each line contains M chars represent the map, include ‘S’,'T’,’.’,'B’.
I promise there must be at least one way from entry to exit.

样例输入:

4
3 3
S..
...
..T

5 5
S....
.B.B.
.....
.B.B.
....T

5 5
S...T
..B..
..B..
..B..
.....

5 5
S...T
..B..
..B..
..B..
..B..

样例输出:

Case 1: 5
S..
...
..T

Case 2: 17
S....
WBWB.
.....
.BWBW
....T

Case 3: 17
S.W.T
W.B.W
..B..
.WBW.
.....

Case 4: 5
S...T
..B..
..B..
..B..
..B..

可以转化成求解一条不能接触的最长路径,拐角处可以接触,如果做过channel的话,这道题相对就简单了,不用记录

(x-1, y-1)是否有路径了。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>   
#include <map>
#include <string>  
#include <climits> 
#include <set>
#include <string>    
#include <sstream>
#include <utility>   
#include <ctime>

using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::stringstream;
using std::make_pair;
using std::getline;
using std::greater;
using std::endl;
using std::multimap;
using std::deque;
using std::random_shuffle;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PAIR;
typedef multimap<int, int> MMAP;
typedef LL TY;

const int MAXN(10010);
const int MAXM(5010);
const int MAXE(10010);
const int MAXK(6);
const int HSIZE(13131);
const int SIGMA_SIZE(26);
const int MAXH(19);
const int INFI((INT_MAX-1) >> 1);
const ULL BASE(31);
const LL LIM(10000000);
const int INV(-10000);
const int MOD(65521);

template<typename T> void checkmax(T &a, T b){if(b > a) a = b;}

template<typename T> void checkmin(T &a, T b){if(b < a) a = b;}

template<typename T> T ABS(const T &a){return a < 0? -a: a;}

int pre[21][10][MAXN], opt[21][10][MAXN];

int MM;

struct HASH_MAP
{
    int first[HSIZE], value[MAXN], next[MAXN];
    LL state[MAXN];
    int size;

    void init()
    {
        memset(first, -1, sizeof(first));
        size = 0;
    }

    void insert(LL ts, int tv, int x, int y, int pid, int op)
    {
        int h = ts%HSIZE;
        for(int i = first[h]; ~i; i = next[i])
            if(state[i] == ts)
            {
                if(tv > value[i])
                {
                    pre[x][y][i] = pid;
                    opt[x][y][i] = op;
                    value[i] = tv;
                }
                return ;
            }
        checkmax(MM, size);
        pre[x][y][size] = pid;
        opt[x][y][size] = op;
        state[size] = ts;
        value[size] = tv;
        next[size] = first[h];
        first[h] = size++;
    }
} hm[2];

HASH_MAP *cur, *last;
int N, M;
int code[11], path[11];  //连通块标号, 是否有路径
int Num[8];
char mp[21][15];


void decode(LL ts)
{
    for(int i = 0; i <= M; ++i)
    {
        code[i] = ts&7;
        path[i] = ts&8;
        ts >>= 4;
    }
}

LL encode()
{
    LL ret = 0;
    memset(Num, -1, sizeof(Num));
    int cnt = 0;
    for(int i = M; i >= 0; --i)
        if(code[i] == 0)
            ret = (ret << 4)|path[i];
        else
        {
            if(Num[code[i]] == -1) Num[code[i]] = ++cnt;
            ret = (ret << 4)|Num[code[i]]|path[i];
        }
    return ret;
}

void updata(int x, int y, int tv, int pid)
{
    int lc = (y == 0)? 0: code[y];
    int uc = (x == 0)? 0: code[y+1];
    int lp = (y == 0)? 0: path[y-1];
    int up = (x == 0)? 0: path[y+1];
    if(mp[x][y] == 'S' || mp[x][y] == 'T')
    {
        if(lc == 0 && uc == 0)
        {
            if(lp || up) return;
            if(x < N-1)
            {
                path[y] = 8;
                code[y] = 7;
                code[y+1] = 0;
                cur->insert(encode(), tv+1, x, y, pid, 1);
            }
            if(y < M-1)
            {
                path[y] = 8;
                code[y] = 0;
                code[y+1] = 7;
                cur->insert(encode(), tv+1, x, y, pid, 1);
            }
        }
        else
            if(lc == 0 || uc == 0)
            {
                if(lc)
                {
                    if(up) return;
                    path[y] = 8;
                    code[y] = code[y+1] = 0;
                    cur->insert(encode(), tv+1, x, y, pid, 1);
                }
                else
                {
                    if(lp) return;
                    path[y] = 8;
                    code[y] = code[y+1] = 0;
                    cur->insert(encode(), tv+1, x, y, pid, 1);
                }
            }
        return;
    }

    if(mp[x][y] == 'B')
    {
        if(lc == 0 && uc == 0)
        {
            path[y] = 0;
            code[y] = code[y+1] = 0;
            cur->insert(encode(), tv, x, y, pid, 0);
        }
        return;
    }
    if(lc == 0 && uc == 0)
    {
        path[y] = 0;
        code[y] = code[y+1] = 0;
        cur->insert(encode(), tv, x, y, pid, 0);
        if(x == N-1 || y == M-1) return;
        if(lp || up) return;
        path[y] = 8;
        code[y] = code[y+1] = 7;
        cur->insert(encode(), tv+1, x, y, pid, 1);
    }
    else
        if(lc == 0 || uc == 0)
        {
            if(lc)
            {
                if(up) return;
                if(x < N-1)
                {
                    path[y] = 8;
                    code[y] = lc;
                    code[y+1] = 0;
                    cur->insert(encode(), tv+1, x, y, pid, 1);
                }
                if(y < M-1)
                {
                    path[y] = 8;
                    code[y] = 0;
                    code[y+1] = lc;
                    cur->insert(encode(), tv+1, x, y, pid, 1);
                }
            }
            else
            {
                if(lp) return;
                if(x < N-1)
                {
                    path[y] = 8;
                    code[y] = uc;
                    code[y+1] = 0;
                    cur->insert(encode(), tv+1, x, y, pid, 1);
                }
                if(y < M-1)
                {
                    path[y] = 8;
                    code[y] = 0;
                    code[y+1] = uc;
                    cur->insert(encode(), tv+1, x, y, pid, 1);
                }
            }
        }
        else
            if(lc != uc)
            {
                path[y] = 8;
                for(int i = 0; i <= M; ++i)
                    if(code[i] == uc) code[i] = lc;
                code[y] = code[y+1] = 0;
                cur->insert(encode(), tv+1, x, y, pid, 1);
            }
}

void solve()
{
    cur = hm;
    last = hm+1;
    last->init();
    last->insert(0, 0, 0, 0, 0, 0);
    for(int i = 0; i < N; ++i)
    {
        int sz = last->size;
        for(int j = 0; j < sz; ++j)
            last->state[j] <<= 4;
        for(int j = 0; j < M; ++j)
        {
            cur->init();
            sz = last->size;
            for(int k = 0; k < sz; ++k)
            {
                decode(last->state[k]);
                updata(i, j, last->value[k], k);
            }
            swap(cur, last);
        }
    }
    int ans = 0, id;
    for(int i = 0; i < last->size; ++i)
    {
        decode(last->state[i]);
        bool flag(true);
        for(int j = 0; j <= M; ++j)
            if(code[j])
            {
                flag = false;
                break;
            }
        if(flag)
        {
            if(last->value[i] > ans)
            {
                ans = last->value[i];
                id = i;
            }
        }
    }
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < M; ++j)
            if(mp[i][j] == '.')
                mp[i][j] = 'W';
    for(int i = N-1; i >= 0; --i)
        for(int j = M-1; j >= 0; --j)
        {
            if(mp[i][j] == 'W' && opt[i][j][id]) mp[i][j] = '.';
            id = pre[i][j][id];
        }
    printf("%d\n", ans);
    for(int i = 0; i < N; ++i)
        printf("%s\n", mp[i]);
    printf("\n");
}

int main()
{
    int TC, n_case(0);
    scanf("%d", &TC);
    while(TC--)
    {
        scanf("%d%d", &N, &M);
        for(int i = 0; i < N; ++i)
            scanf("%s", mp[i]);
        printf("Case %d: ", ++n_case);
        solve();
    }
    return 0;
}

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

参考:http://blog.csdn.net/gyarenas/article/details/9454525


  1. 话说刺客信条是根据真实历史改编的,总部的那个老大就是著名的恐怖主义始祖山中老人霍山,后来刺客联盟阿萨辛派被镇压后教义仍留于世,现在最有名的继承者有本拉登还有东突分子等,啊稍等有人敲门抄水表

  2. 最后的一个“好心的”附注真是破坏了一切,你不如再加一句“bitch就是婊子”。还可以再加一句“婊子就是作风不检点的女人”。