zoj_1002(Fire Net)的一个简单的解法

做了一天，把此题AC了，看到网上用的算法很复杂，发个自己的出来。
思路：
1.如果城市全空，可以不管顺序，随便从哪里开始放“碉堡”，把“碉堡”射程里的城市标记下，后面的“碉堡”不放在这里即可得到结果。
2.但是如果城市中有“墙”的话，就不可以按照1的方法了，因为放置数量的多少与顺序是有关的，所以，怎样来确定这个顺序是很重要的。观察发现，城市里的空地按照领域中的“墙”的数量可以分为五种，即从0到4。再观察，可以得到这样一个结论：按邻域中墙的数目由多到少，往空地上安放“碉堡”，可以使数目最大！
于是按照这个结论，编程如下：

个人水平有限，代码编得很烂。。。
 

#include 
#include 
#include 
using namespace std;
int main()
{
  int size;
  vector nums;
  vector sort;
  int max=0;
  char *matrix;
  ostringstream buff;
    while(1)
    {
        cin>>size;
        if(size==0)break;
        //读入成一维数组
        matrix=new char[size*size];
        max=0;
        //接受输入
        for(int i=0;i v4,v3,v2,v1,v0;
    for (int i=0;ii/size*size && matrix[i-1]=='X')count++;
        if(i+size=0 && matrix[i-size]=='X')count++;
        switch (count)
        {
          case 0:
            v0.push_back(i);
            break;
          case 1:
            v1.push_back(i);
            break;
          case 2:
            v2.push_back(i);
            break;
          case 3:
            v3.push_back(i);
            break;
 &
nbsp;        case 4:
            v4.push_back(i);
            break;
        }
      }
    }
    nums.insert(nums.end(),v0.begin(),v0.end());
    nums.insert(nums.end(),v1.begin(),v1.end());
    nums.insert(nums.end(),v2.begin(),v2.end());
    nums.insert(nums.end(),v3.begin(),v3.end());
    nums.insert(nums.end(),v4.begin(),v4.end());
      //开始处理
      int apos;
      while(!nums.empty())
      {
        apos=nums.back();
        nums.pop_back();
        //这是射击范围内的点
        if(matrix[apos]=='0')
        {
          continue;
        }
        max++;//数块数
        //向四个方向标记射击区域，用0来标记
        int tapos;
      tapos=apos;
        while(1)
        {
          if(tapos>apos/size*size+size-1 || matrix[tapos]=='X')break;
          matrix[tapos]='0';
        tapos++;
        }
      tapos=apos;
        while(1)
        {
          tapos--;
          if(tapossize*size-1 || matrix[tapos]=='X')break;
          matrix[tapos]='0';
        }
      tapos=apos;
        while(1)
        {
          tapos-=size;
          if(tapos<0 || matrix[tapos]=='X')break;
          matrix[tapos]='0';
        }
      }
      delete[] matrix;
      buff< 

Share this:
Facebook
X
Like this:
Like Loading...


	
Related