岛上的植物(湖南省第二届大学生程序设计大赛) -- 编程驿站-- 编程爱好者博客

岛上的植物

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

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

博客介绍

正文

岛上的植物(湖南省第二届大学生程序设计大赛)2007-08-19 10:40:00

评论