首页 > 搜索 > BFS搜索 > hdu 2392 Robotic Invasion-BFS[解题报告]C++
2014
01-05

hdu 2392 Robotic Invasion-BFS[解题报告]C++

Robotic Invasion

问题描述 :

The pacifistic people of planet Pax are at war with the evil guys from planet Googol. Although they are strictly pacifistic they have means of defense. Their cryptographers are able to routinely decrypt the commands sent to Googol’s robots and they can � using huge amounts of energy � construct bogus commands. It is the job of the Tactical Unit Defense (TUD) to find the best way to interfere with the command transmission from Googol.

You are given a string of movements (each being a step to the north, east, south or west) and a map containing an invading robot from Googol and, possibly, several obstacles and traps.
Your task is to find a way to overcome the threat by changing as few movements as possible and guiding the robot into a trap. A single change replaces a step by another direction or no movement at all.
A robot will move in the given direction if the position is not blocked or outside the given map. If given such a direction, the robot does not move instead.

输入:

The first line contains the number of scenarios. For each scenario a line containing two integers 1 <= w; h <= 100 separated by a single space is given, followed by h lines each containing w characters. This is a map of the area.
Exactly one character is a R which is the starting position of the invading robot. Other characters are ‘.’ to denote free positions, X to denote blocked positions and + to denote traps.
This is followed by a line containing an integer 0 <= c <= 100 and another line containing c characters of communication. Each character is either N, E, S or W to denote a command to move one position up, right, down or left, respectively.

输出:

The first line contains the number of scenarios. For each scenario a line containing two integers 1 <= w; h <= 100 separated by a single space is given, followed by h lines each containing w characters. This is a map of the area.
Exactly one character is a R which is the starting position of the invading robot. Other characters are ‘.’ to denote free positions, X to denote blocked positions and + to denote traps.
This is followed by a line containing an integer 0 <= c <= 100 and another line containing c characters of communication. Each character is either N, E, S or W to denote a command to move one position up, right, down or left, respectively.

样例输入:

3
3 2
R+.
...
3
EEE
3 3
R..
.X+
...
3
SSE
3 3
R..
..+
...
3
SSE

样例输出:

Scenario #1:
EEE

Scenario #2:
EES

Scenario #3:
ESE

#include <stdio.h>
#include <string.h>
#define INF (1 << 30)
char fx[5] = {'N', 'E', 'S', 'W', 'X'};
int yd[5][2] = {0, -1,
                1, 0,
                0, 1,
                -1, 0,
                0, 0};
typedef struct {
    int x, y, z;
}Point;
char map[110][110], s[110];
int dp[100][100][100], lj[100][100][100], dl[1000000], beg, endx;
int n, m, stp, endint;
Point source, end;
void getPath(int x,int y,int s,char str[]){
    int d;
    if(s==0) return;
    getPath(x-yd[d][0],y-yd[d][1],s-1,str);
    str[s-1]=fx[d];
    str[s]=0;
}
void bfs() {
    int i;
    endint = INF;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            for(int l = 0; l < 100; ++l) {
                dp[i][j][l] = INF;
            }
        }
    }
    char nows[100], nexts[100];
    Point now, next;
    int tmp;
    dl[0] = (source.x << 20) + (source.y << 10) + 0;
    beg = endx = 0;
    while(beg <= endx) {
        now.x = (dl[0] >> 20);
        now.y = (dl[0] >> 10) & 1023;
        now.z = dl[0] & 1023;
        for(i = 0; i < 5; ++i) {
            next.x = now.x + yd[i][0]; 
            next.y = now.y + yd[i][1];
            next.z = now.z + 1;
            tmp = dp[now.x][now.y][now.z]; 
            if(s[now.z] != fx[i]) tmp++;
            if(map[next.x][next.y] != 'X') {
                if(dp[next.x][next.y][next.z] > tmp) {
                    if(dp[next.x][next.y][next.z] != INF) {
                        dl[++endx] = dl[0] = (next.x << 20) + (next.y << 10) + next.z;
                    }
                    dp[next.x][next.y][next.z] = tmp;
                    lj[next.x][next.y][next.z] = i;
                } else if(dp[next.x][next.y][next.z] == tmp) {
                    getPath(next.x, next.y, next.z, nows);
                    
                    getPath(now.x, now.y, now.z, nexts);
                    nexts[now.z - 1] = fx[i];
                    nexts[now.z] = 0;
                    
                    if(strcmp(nows, nexts) > 0) {
                        lj[next.x][next.y][next.z] = i;
                    }
                }
                if(map[next.x][next.y] != '+') {
                    if(dp[next.x][next.y][next.z] < endint) {
                        endint = dp[next.x][next.y][next.z];
                        end.x = next.x;
                        end.y = next.y;
                        end.z = next.z;
                    } else if(dp[next.x][next.y][next.z] == endint) {
                        getPath(next.x, next.y, next.z, nows);
                        getPath(end.x, end.y, end.z, nexts);   
                        if(strcmp(nows, nexts) > 0) {
                            endint = dp[next.x][next.y][next.z];
                            end.x = next.x;
                            end.y = next.y;
                            end.z = next.z;
                        }                  
                    }
                }
            }
        }
        beg++;
    }
}

int main() {
    int t;
    scanf("%d", &t);
    for(int tt = 0; tt < t; ++tt) {
        scanf("%d %d", &m, &n);
        for(int i = 0; i < n; ++i) scanf("%s", map[i]);
        scanf("%d", &stp);
        scanf("%s", s);
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(map[i][j] == 'R') {
                    source.x = i;
                    source.y = j;
                    source.z = 0;
                    break;
                }
            }
        }
        bfs();
        
    }
    return 0;
}

 


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。