题目(3)
思路
广搜。每次找到现在的最高点,向四周扩散,直到无法扩散为止。走完所有后输出解即可。
#include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<cstring> using namespace std; char a[51][51][6],c; int m[6],n[6],sum=0,time1; bool b[51][51][6]; void bfs(int x,int y,int i1) { if(x<1||x>n[i1]||y<1||y>m[i1])//过界 return ; b[x][y][i1]=true; if(a[x][y][i1]<=a[x-1][y][i1])//上 if(b[x-1][y][i1]==false) bfs(x-1,y,i1); if(a[x][y][i1]<=a[x][y-1][i1])//左 if(b[x][y-1][i1]==false) bfs(x,y-1,i1); if(a[x][y][i1]<=a[x][y+1][i1])//右 if(b[x][y+1][i1]==false) bfs(x,y+1,i1); if(a[x][y][i1]<=a[x+1][y][i1])//下 if(b[x+1][y][i1]==false) bfs(x+1,y,i1); } int main() { memset(b,false,sizeof(b)); scanf("%d",&time1); for(int i1=1;i1<=time1;i1++) { scanf("%d%d",&n[i1],&m[i1]); for(int i=1;i<=n[i1];i++) for(int j=1;j<=m[i1];j++) cin>>a[i][j][i1]; } for(int i1=1;i1<=time1;i1++) { sum=0; for(int i=26;i>=1;i--) { c='z'-i+1;//最高点搜起 for(int j=1;j<=n[i1];j++) for(int k=1;k<=m[i1];k++) if(a[j][k][i1]==c) if(b[j][k][i1]==false) { bfs(j,k,i1); sum++; } } cout<<sum<<endl; } return 0; }
血与泪的教训:再也不用英文单词了,time尽然是函数,100分离我远去了!!!!