首页 > 搜索 > BFS搜索 > HDU 4141-Crank-DFS-[解题报告]HOJ
2015
04-16

HDU 4141-Crank-DFS-[解题报告]HOJ

Crank

问题描述 :

Chev Chelios had his heart stolen from him, by the boss of the most dangerous gang in the city. His heart has been replaced with an artificial chargeable one!
Chelios was on mission of locating the boss of the gang to get his heart back since then without luck! Now the artificial heart’s battery lifetime is about to expire! Fortunately, he finally located the target but he needs your help to get there before his artificial heart stops beating!
Chelios decided to attack the boss building from the roof because all gates are heavily protected by gangsters. Chelios has the map of the gang block which shows the heights of all buildings within the block. The plan is that a helicopter will drop Chelios on the roof of one of the buildings on the boundary of the block during night. Then Chelios will get to the boss building by moving to adjacent buildings, vertically or horizontally. Chelios can only move to a building which has the same or smaller height as the current building (going up severely affects his damaged heart).
Given the gang building block map which shows the heights of all buildings in the block along with the boss building, write a program to help Chev Chelios determine the number of buildings on the boundary of the block he can be dropped by the helicopter at so that he would be able to reach the boss’s building without climbing!

输入:

The first line of input contains an integer T, the number of test cases. T test cases follow, the first line of each test case contains two integers (1 <= R,C <= 10) the height and width of the building block. The second line contains two integers (1 <= A <= R), and (1 <= B <= C), the coordinates of the boss building on the map. R lines follows; each line consists of C space separated integers representing the heights of all buildings. A height H of a building satisfies (1 <= H <= 1000).

输出:

The first line of input contains an integer T, the number of test cases. T test cases follow, the first line of each test case contains two integers (1 <= R,C <= 10) the height and width of the building block. The second line contains two integers (1 <= A <= R), and (1 <= B <= C), the coordinates of the boss building on the map. R lines follows; each line consists of C space separated integers representing the heights of all buildings. A height H of a building satisfies (1 <= H <= 1000).

样例输入:

2
3 3
2 2
1 7 3
2 6 3
3 5 4
2 2
2 1
2 7
2 6

样例输出:

Case #1: 1
Case #2: 4

简单的dfs,bfs也可以

int g[11][11];
int n,m;
bool vis[11][11];
int d[4][2] = {0,1,0,-1,1,0,-1,0};
int ans;
void dfs(int x,int y){
    if(vis[x][y])return ;
    vis[x][y] = 1;
    int i;
    if(x==1 || y==1 || x==n || y==m)
        ans++;
    for(i=0;i<4;i++){
        int xx = x+d[i][0];
        int yy = y+d[i][1];
        if(xx<1 || yy<1 || xx>n || yy>m)continue;
        if(g[xx][yy]>=g[x][y]){
            dfs(xx,yy);
        }
    }
}
int main(){
    int t;
    scanf("%d",&t);
    int ca=1;
    while(t--){
        scanf("%d%d",&n,&m);
        int i,j;
        int s,t;
        scanf("%d%d",&s,&t);
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%d",&g[i][j]);
                vis[i][j] = 0;
            }
        }
        ans = 0;
        dfs(s,t);
        printf("Case #%d: %d\n",ca++,ans);
    }
    return 0;
}

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

参考:http://blog.csdn.net/leolin_/article/details/7306552


, ,
  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。