水流(water)
时间限制: 1 Sec内存限制: 64 MB
提交: 9解决: 2
[提交][状态][讨论版]
题目描述
全球气候变暖,小镇A面临水灾,于是你必须买一些泵把水抽走。泵的抽水能力可以认为是无穷大,但你必须把泵放在合适的位置,从而能使所有的水能流到泵里。 小镇可以认为是N×M的矩阵,矩阵里的每个单元格都是一个a~z小写字母,该小写字母表示该格子的高度,字母大的表示该单元格比较高,反之表示该格子高度 比较低。当前单元格的水可以流到上、下、左、右四个格子,但必须满足这些格子的高度是小于或者等于当前格子的高度。现在,给你一些NXM的矩阵,你至少要 买多少个泵,才能把所有格子的水都抽走?
输入
多组测试数据。
第1行:K,表示有K组测试数据,1≤K≤5。
接下来有K组测试数据,每组测试数据格式如下:
第1行:两个正整数,N,M。1≤N,M≤50,表示小镇的大小。
接下来有N行,每行有M个小写字母,表示小镇的地图。
输出
共K行,每行对应一组数据。至少要买多少个泵,才能把所有格子的水都抽走。
样例输入
2
5 5
ccccc
cbbbc
cbabc
cbbbc
ccccc
4 9
cbabcbabc
cbabcbabc
cbabcbabc
cbabcbabc
样例输出
1
2
【分析】我是用BFS写的,从z遍历到a,我们实验室有位大神用DFS过了一发,不过时间比我长,下面是两段AC代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define inf 0x3f3f3f3f
#define mod 1000000007
typedef long long ll;
using namespace std;
const int N=55;
int n,dp[N],len;
string w[N];
int vis[N][N];
int m,t;
int d[4][2]={1,0,0,1,-1,0,0,-1};
set<int>p;
int minn=inf;
struct man {
int x,y;
int st;
};
queue<man>q;
void bfs(int aa,int bb,char ch) {
man s;s.x=aa;s.y=bb;s.st=ch;q.push(s);
vis[aa][bb]=1;
while(!q.empty())
{
man t=q.front();q.pop();
for(int i=0;i<4;i++)
{
int xx=t.x+d[i][0],yy=t.y+d[i][1];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&w[xx][yy]>=t.st&&vis[xx][yy]==0)
{
man k;k.x=xx;k.y=yy;k.st=w[xx][yy];vis[xx][yy]=1;q.push(k);
}
}
}
}
int main() {
cin>>t;
while(t--) {
int ans=0;
while(!q.empty())q.pop();
memset(vis,0,sizeof(vis));
cin>>n>>m;
for(int i=0; i<n; i++)cin>>w[i];
for(char ch='a'; ch<='z'; ch++) {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(w[i][j]==ch&&vis[i][j]==0)
{
ans++;
bfs(i,j,ch);
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
BFS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include <climits>
#include <map>
using namespace std;
const int MAXN = 53;
int N, M;
char maze[MAXN][MAXN];
char s[MAXN][MAXN];
int xi[] = {0, 0, -1, 1};
int yi[] = {1, -1, 0, 0};
void dfs(int x, int y) {
s[x][y] = 1;
for(int i = 0; i < 4; i++) {
int nx = x + xi[i];
int ny = y + yi[i];
//printf("%d %d %cn", nx, ny,maze[nx][ny]);
if(nx>=0 && nx < N && ny >= 0 && ny < M && s[nx][ny] == 0 && maze[nx][ny] >= maze[x][y]) {
dfs(nx, ny);
}
}
}
int main() {
int t = 0;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("%s", maze[i]);
}
memset(s, 0, sizeof(s));
int cnt = 0;
for(char c = 'a'; c <= 'z'; c++) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(s[i][j] == 0 && maze[i][j] == c){
dfs(i, j);
cnt++;
}
}
}
}
printf("%dn", cnt);
}
return 0;
}
DFS
原文链接: https://www.cnblogs.com/jianrenfang/p/5722569.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/237931
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!