2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Дискретная Математика - задача
Сообщение25.12.2008, 16:56 
Может кто-нибудь может помочь? очень сильно надо, чем быстрее, тем лучше)

Изображение

 
 
 
 
Сообщение26.12.2008, 20:23 
Попробуйте следующий код, правда, я не совсем уверен в его
полной корректности - потестируйте на экзотических конфигурациях
музея. Кроме того, существенен ли порядок печати площадей комнат?
Так, для вашего тестового примера этот порядок будет таким:
9 3 8 2 6 вместо 9 6 3 2 8.

Код:
#include <iostream>
using namespace std;

int  num, **mark, **muzeum, *summa;

void FloodFill(int x, int y)
{
  int n;

  mark[x][y] = num;
  n          = muzeum[x][y];

  if((n & 1) == 0 && mark[x][y - 1] == 0)
    FloodFill(x, y - 1);
  if((n & 2) == 0 && mark[x - 1][y] == 0)
    FloodFill(x - 1, y);
  if((n & 4) == 0 && mark[x][y + 1] == 0)
    FloodFill(x, y + 1);
  if((n & 8) == 0 && mark[x + 1][y] == 0)
    FloodFill(x + 1, y);
}

int main(int argc, char *argv[])
{
  int i, j, n1, n2;

  cout << "?";

  cin >> n1 >> n2;
  mark   = new int *[n1];
  muzeum = new int *[n1];

  for(i = 0; i < n1; ++i)
  {
    mark[i]   = new int[n2];
    muzeum[i] = new int[n2];
    for(j = 0; j < n2; ++j)
    {
      cin >> muzeum[i][j];
      mark[i][j] = 0;
    }
  }

  for(i = 0; i < n1; ++i)
  {
    for(j = 0; j < n2; ++j)
    {
      if(mark[i][j] == 0)
      {
        ++num;
        FloodFill(i, j);
      }
    }
  }

  summa = new int[num];
  for(i = 0; i < num; ++i)
  {
    summa[i] = 0;
  }

  for(i = 0; i < n1; ++i)
  {
    for(j = 0; j < n2; ++j)
    {
      ++summa[mark[i][j] - 1];
    }
  }

  cout << num << '\n';
  for(i = 0; i < num; ++i)
  {
    cout << summa[i] << ' ';
  }
  cout << '\n';

  for(i = 0; i < n1; ++i)
  {
    delete[] mark[i];
    delete[] muzeum[i];
  }

  delete[] mark;
  delete[] muzeum;
  delete[] summa;

  return 0;
}

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group