首页 > 博弈论 > hdu 1122 Direct Visibility-记忆化搜索-[解题报告]
2013
11-28

hdu 1122 Direct Visibility-记忆化搜索-[解题报告]

Direct Visibility

问题描述 :

Building the GSM network is a very expensive and complex task. Moreover, after the Base Transceiver Stations (BTS) are built and working, we need to perform many various measurements to determine the state of the network, and propose effective improvements to be made.
The ACM technicians have a special equipment for measuring the strength of electro-magnetic fields, the transceivers’ power and quality of the signal. This equipment is packed into a huge knapsack and the technician must move with it from one BTS to another. Unfortunately, the knapsack have not enough memory for storing all of the measured values. It has a small cache only, that can store values for several seconds. Then the values must be transmitted to the BTS by an infrared connection (IRDA). The IRDA needs direct visibility between the technician and the BTS.

Your task is to find the path between two neighbouring BTSes such that at least one of those BTSes is always visible.

输入:

There is a single positive integer T on the first line of input. It stands for the number of test cases to follow. Each test case consists of a town description. For simplicity, a town is modelled as a rectangular grid of P x Q square fields. Each field is exactly 1 metre wide. For each field, a non-negative integer Zi,j is given, representing the height of the terrain in that place, in metres. That means the town model is made of cubes, each of them being either solid or empty. There are no "half solid" cubes.

The first line of each test case contains two integer numbers P and Q, separated by a single space, 1 <= P, Q <= 200. Then there are P lines each containing Q integer numbers separated by a space. These numbers are Zi,j, where 1 <= i <= P, 1 <= j <= Q and 0 <= Zi,j <= 5000. After the terrain description, there are four numbers R1, C1, R2, C2 on the last line of each test case. These numbers represent position of two BTSes, 1 <= R1, R2 <= P, 1 <= C1, C2 <= Q. The first coordinate (R) determines the row of the town, the second coordinate determines the column.

The technician is moving in steps (steps stands for Standard Technician’s Elementary Positional Shift). Each step is made between two neighbouring square fields. That means the step is always in North, South, West or East direction. It is not possible to move diagonally. The step between two fields A and B (step from A to B) is allowed only if the height of the terrain in the field B is not very different from the height in the field A. The technician can climb at most 1 metre up or descend at most 3 metres down in a single step.

At the end of each step, at least one of the two BTSes must be visible. However, there can be some point "in the middle of the step" where no BTS is visible. This is OK and the data is handled by the cache. The BTS is considered visible, if there is a direct visibility between the unit cube just above the terrain on the BTSes coordinates and the cube just above the terrain on the square field, where the technician is. Direct visibility between two cubes means that the line connecting the centres of the two cubes does not intersect any solid cube. However, the line can touch any number of solid cubes. In other words, consider both the BTS and the technician being points exactly half metre above the surface and in the centre of the appropriate square field.

Note that the IRDA beam can go between two cubes that touch each other by their edge, although there is no space between them. It is because such a beam touches both of these two cubes but does not intersect any of them. See the last test case of the sample input for an example of such a situation.

输出:

You are to find the shortest possible path meeting the above criteria. All steps must be done between neighbouring fields, the terrain must not elevate or descend too much, and at the end of each step, at least one BTS must be visible.

For each test case, print one line containing the sentence The shortest path is M steps long., where M is the number of steps that must be made. If there is no such path, output the sentence Mission impossible!.

样例输入:

4
5 5
8 7 6 5 4
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
1 1 5 1
5 8
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 2
2 2 2 2 2 2 2 2
1 2 5 1
5 8
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 2
2 2 2 2 2 2 2 2
1 5 5 1
6 12
5 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 1 5 5 5 5 5 5 5
5 5 5 5 9 5 5 5 5 5 5 5
5 9 1 5 5 5 5 5 5 5 5 5
5 5 9 5 5 5 5 5 5 5 5 5
5 5 9 5 5 5 5 5 5 5 5 5
6 1 3 12

样例输出:

The shortest path is 10 steps long.
Mission impossible!
The shortest path is 14 steps long.
The shortest path is 18 steps long.

比较经典的一道题目,涉及搜索的博弈题一般都会用到记忆化来降低复杂度。一开始没记忆化果断超时了啊,3s实现记忆化后0.07s AC


#include <iostream>
#include <stdio.h>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#define M 25
#define For(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
int n;
int s[M];
int d[M];
int t;
int dp[1 << 21];

int change(int x, int k) {
    for (int i = k; i < 21; i += k) {
        x |= d[i];
        for (int j = 2; j + i < 21; j++) {
            if (x & d[j]) {
                x |= d[i + j];
            }
        }
    }
    return x;
}

int dfs(int x) {
    if (x == t)
        return 1;
    if (dp[x] != -1) {
        return dp[x];
    }
    int num = 0;
    int ff;

    For(i, 0, n) {
        if ((x & d[s[i]]) == 0) {
            ff = change(x, s[i]);
            num += dfs(ff);
        }
    }
    if (num == 0) {
        dp[x] = 1;
        return 1;
    } else { dp[x] = 0;
        return 0;
       
    }
}
int ans[M];

int main(int argc, char** argv) {
    int cs = 0;
    t = (1 << 21) - 1;

    For(i, 0, 22) {
        d[i] = 1 << i;
    }
    while (scanf("%d", &n), n) {
        memset(dp, -1, sizeof (dp));
        int f = (1 << 21) - 1;
        cs++;
        For(i, 0, n)
        scanf("%d", &s[i]), f ^= d[s[i]];
        int now;
        int cnt = 0;
        int tmp;

        For(i, 0, n) {
            tmp = change(f, s[i]);
            now = dfs(tmp);
            if (now)
                ans[cnt++] = s[i];
        }
        printf("Test Case #%d\n", cs);
        if (cnt == 0) {
            printf("There's no winning move.\n\n");
            continue;
        }
        printf("The winning moves are:");
        sort(ans, ans + cnt);
        For(i, 0, cnt)
        printf(" %d", ans[i]);
        printf("\n\n");
    }
    return 0;
}

解题转自:http://zhulinb123.blog.163.com/blog/static/18441404320125161354537/


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. [email protected] on said:

    代码不对,仔细对比一下输入输出, 怎么会有‘‘printf("The winning moves are:");’’这种输出呢?

  3. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.