首页 > 搜索 > DFS搜索 > hdu 2488 Tornado-DFS-[解题报告]C++
2014
01-26

hdu 2488 Tornado-DFS-[解题报告]C++

Tornado

问题描述 :

Professor Jonathan is a well-known Canadian physicist and meteorologist. People who know him well call him “Wind Chaser”. It is not only because of his outstanding tornado research which is the most influential in the academic community, but also because of his courageous act in collecting real data of tornados. Actually he has been leading his team chasing tornado by cars equipped with advanced instruments hundreds of times.

In summer, tornado often occurs in the place where Professor Jonathan lives. After several years of research, Wind Chaser found many formation rules and moving patterns of tornados. In the satellite image, a tornado is a circle with radius of several meters to several kilometers. And its center moves between two locations in a straight line, back and forth at a fixed speed. After observing a tornado’s movement, Wind Chaser will pick a highway, which is also a straight line, and chase the tornado along the highway at the maximum speed of his car.

The smallest distance between the Wind Chaser and the center of the tornado during the whole wind chasing process, is called “observation distance”. Observation distance is critical for the research activity. If it is too short, Wind Chaser may get killed; and if it is too far, Wind Chaser can’t observe the tornado well. After many times of risk on lives and upset miss, Wind Chaser turns to you, one of his most brilliant students, for help. The only thing he wants to know is the forthcoming wind chasing will be dangerous, successful or just a miss.

输入:

Input contains multiple test cases. Each test case consists of three lines which are in the following format.

xw1 yw1 xw2 yw2 vw
xt1 yt1 xt2 yt2 vt
dl du

In the first line, (xw1, yw1) means the start position of Wind Chaser; (xw2, yw2) is another position in the highway which Wind Chaser will definitely pass through; and vw is the speed of the car. Wind chaser will drive to the end of the world along that infinite long highway.
In the second line, (xt1, yt1) is the start position of tornado; (xt2, yt2) is the turn-around position and vt is the tornado’s speed. In other words, the tornado’s center moves back and forth between (xt1, yt1) and (xt2, yt2) at speed vt .

The third line shows that if the observation distance is smaller than dl , it will be very dangerous; and if the observation distance is larger than du, it will be a miss; otherwise it will lead to a perfect observation.

All numbers in the input are floating numbers.

-2000000000 <= xw1, yw1, xw2, yw2, xt1, yt1, xt2, yt2 <= 2000000000
1 <= vw, vt <= 20000
0 <= dl, du <= 2000000

Note:
1.  It’s guaranteed that the observation distance won’t be very close to dl or du during the whole wind chasing process. There will be at least 10-5 of difference.
2.  Wind Chaser and the tornado start to move at the same time from their start position.

输出:

Input contains multiple test cases. Each test case consists of three lines which are in the following format.

xw1 yw1 xw2 yw2 vw
xt1 yt1 xt2 yt2 vt
dl du

In the first line, (xw1, yw1) means the start position of Wind Chaser; (xw2, yw2) is another position in the highway which Wind Chaser will definitely pass through; and vw is the speed of the car. Wind chaser will drive to the end of the world along that infinite long highway.
In the second line, (xt1, yt1) is the start position of tornado; (xt2, yt2) is the turn-around position and vt is the tornado’s speed. In other words, the tornado’s center moves back and forth between (xt1, yt1) and (xt2, yt2) at speed vt .

The third line shows that if the observation distance is smaller than dl , it will be very dangerous; and if the observation distance is larger than du, it will be a miss; otherwise it will lead to a perfect observation.

All numbers in the input are floating numbers.

-2000000000 <= xw1, yw1, xw2, yw2, xt1, yt1, xt2, yt2 <= 2000000000
1 <= vw, vt <= 20000
0 <= dl, du <= 2000000

Note:
1.  It’s guaranteed that the observation distance won’t be very close to dl or du during the whole wind chasing process. There will be at least 10-5 of difference.
2.  Wind Chaser and the tornado start to move at the same time from their start position.

样例输入:

0 0 1 0 2
10 -5 12 7 4
1.3 2.7
0 0 1 0 2
10 -5 12 7 1
0.3 0.4

样例输出:

Dangerous
Perfect

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int path[88][88], vis[88][88], p, q, cnt;
bool flag;

int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2};

bool judge(int x, int y)
{
    if(x >= 1 && x <= p && y >= 1 && y <= q && !vis[x][y] && !flag)
        return true;
    return false;
}

void DFS(int r, int c, int step)
{
    path[step][0] = r;
    path[step][1] = c;
    if(step == p * q)
    {
        flag = true;
        return ;
    }
    for(int i = 0; i < 8; i++)
    {
        int nx = r + dx[i];
        int ny = c + dy[i];
        if(judge(nx,ny))
        {

            vis[nx][ny] = 1;
            DFS(nx,ny,step+1);
            vis[nx][ny] = 0;
        }
    }
}

int main()
{
    int i, j, n, cas = 0;
    scanf("%d",&n);
    while(n--)
    {
        flag = 0;
        scanf("%d%d",&p,&q);
        memset(vis,0,sizeof(vis));
        vis[1][1] = 1;
        DFS(1,1,1);
        printf("Scenario #%d:\n",++cas);
        if(flag)
        {
            for(i = 1; i <= p * q; i++)
                printf("%c%d",path[i][1] - 1 + 'A',path[i][0]);
        }
        else
            printf("impossible");
        printf("\n");
        if(n != 0)
            printf("\n");
    }
    return 0;
}

解题转自:http://blog.csdn.net/lyhvoyage/article/details/18355471


,
  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks