2015
04-16

# 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

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;
}

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();}.