岛上的植物 Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB Total submit users: 31, Accepted users: 26 Problem 10844 : No special judgement Problem description 测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数，代表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型，元素为合数时对应土地上的植物为常见类型。为保护稀有植物，林业局雇佣你编写程序分析上述数值方阵，从中检测出稀有植物区和非稀有植物区。划分区域的原则是：如果数值方阵中的两个元素同为质数或同为合数，而且它们共行相邻或共列相邻，则这两个元素同属一个区域。 Input 输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行，同一行的方阵元素之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数，代表该方阵的行数。文件的结尾行包含且仅包含一个负整数。数值方阵的行数不会超过100，元素的值不会大于100000000。 Output 针对输入文件中的每一个数值方阵分别输出如下信息： 1 该数值方阵的序号（按照其在输入文件中的位置从1计起）。格式是：“Area n:” (n代表方阵序号) 2 稀有植物区域的数目和每个稀有植物区域的面积（按升序排列）。格式是： “M unique vegetation regions: a1 a2 ...” (M为区域数目，a1, a2,...等代表每个区域的面积) 3 非稀有植物区域的数目。格式是：“K non-unique vegetation regions” (K为区域数目) 具体的输出格式请参考示例。 Sample Input 3 2 4 9 17 6 37 29 8 11 4 2 3 12 15 5 7 21 33 4 6 11 17 8 9 13 29 -1 Sample Output Area 1: 2 unique vegetation regions: 2 3 1 non-unique vegetation regions Area 2: 2 unique vegetation regions: 4 4 2 non-unique vegetation regions Problem Source 湖南省第二届大学生程序设计大赛 ////// 递归搜索题#include <iostream> #include <algorithm> #include <cmath> #include <vector> #define MAX 100 using namespace std; bool isPrime(int a){ if(a==1) return false; for(int i=2; i<=sqrt(a); i++){ if(!(a%i)) return false; } return true; } int myCmp(const void *a, const void *b){ if(*(int*)a > *(int*)b) return -1; else if(*(int*)a < *(int*)b) return 1; return 0; } int get(char a[][MAX],int i,int j,int n){ int k=a[i][j],sum=0; a[i][j] = 0; if(a[i-1][j] && i>0 && k==a[i-1][j]) sum += get(a,i-1,j,n); if(a[i+1][j] && i<n-1 && k==a[i+1][j]) sum += get(a,i+1,j,n); if(a[i][j-1] && j>0 && k==a[i][j-1]) sum += get(a,i,j-1,n); if(a[i][j+1] && j<n-1 && k==a[i][j+1]) sum += get(a,i,j+1,n); return sum+1; } int main() { char a[MAX][MAX]={0}; int test=1; vector<int> v; while(1){ int n,i,j,k; cin>>n; if(n==-1) break; for(i=0; i<n; i++){ for(j=0; j<n; j++){ cin>>k; if(isPrime(k)) a[i][j]=1; else a[i][j]=2; } } for(k=i=0; i<n; i++){ for(j=0; j<n; j++) if(a[i][j]>0){ if(a[i][j]==1) v.push_back(get(a,i,j,n)); else{ get(a,i,j,n); k++; } } } cout<<"Area "<<test++<<":"<<endl; cout<<v.size()<<" unique vegetation regions:"; sort(v.begin(),v.end()); for(i=0; i<v.size(); i++) cout<<" "<<v[i]; cout<<endl<<k<<" non-unique vegetation regions"<<endl; v.clear(); } return 0; }
评论