列表

详情

NC220471. EfficientlyElevated

描述

    You are an employee of the Brussels Architectural Projects Consultancy in charge of ensuring all building designs meet the accessibility requirements. As law dictates, every part of your building should be reachable for wheelchair users, which means elevators will have to be installed. You are given the blueprints of the company's current project and have to determine the minimum number of elevators required.

    The floor plan is laid out on a square grid and the blueprints tell you the number of floors above any given square. You can place an elevator at any square, which stops at all floors of that square. A wheelchair user can move up and down between floors using the elevators and can freely move to any of the four adjacent squares on the same floor. Buildings do not connect diagonally.

    The figure shows the second sample input. Designs can consist of multiple buildings; this one contains three buildings. The design requires two elevators: one for the pyramid-shaped building and one for the tall tower. The small building of height one does not require an elevator, since it only has a ground floor.

 A visualisation of the second sample input.

输入描述

The input consists of:
- One line containing integers  and  (), the height and width of the grid.
-  lines of  integers each, where  (), the th integer on the th line, denotes the number of floors at position  of the grid.

输出描述

Output the minimum number of elevators you need to build to be able to reach every part of the building(s) in the grid.

示例1

输入: 

3 3
1 2 3
0 0 4
7 6 5

输出: 

1

示例2

输入: 

6 7
0 0 0 0 0 0 0
0 1 2 3 2 1 0
0 1 2 3 2 1 0
0 0 0 0 0 0 0
0 1 0 5 0 0 0
0 0 0 0 0 0 0

输出: 

2

示例3

输入: 

4 4
1 1 2 1
2 2 1 2
1 2 2 1
2 1 2 2

输出: 

4

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 114ms, 内存消耗: 37244K, 提交时间: 2021-04-08 13:03:00 

#include <bits/stdc++.h>
using namespace std;

int i,j,k,n,m,res,a[505][505];
vector<vector<int> >v;

void dfs(int x,int y){
	if(!a[x][y]){return;}
	//printf("%d %d\n",x,y);
	int tmp=a[x][y];a[x][y]=0;
	if(a[x-1][y]<=tmp){dfs(x-1,y);}
	if(a[x+1][y]<=tmp){dfs(x+1,y);}
	if(a[x][y-1]<=tmp){dfs(x,y-1);}
	if(a[x][y+1]<=tmp){dfs(x,y+1);}
}

int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]==1){a[i][j]=0;}
			v.push_back({-a[i][j],i,j});
		}
	}
	sort(v.begin(),v.end());
	for(auto i:v){
		if(a[i[1]][i[2]]){dfs(i[1],i[2]);res++;}
	}
	printf("%d",res);
}

上一题

© 2024 nowcoder.com