SGU - 344 (Weed)

[=[miKroZ]=]

Вот задача.

Мой алгоритм такой: ищем связные куски на поле и накладываем на них прямоугольник (минимального размера, понятно, что в какой-то момент получиться так). затем пробегаю по полю, нахожу ситуации вида X.X и запускаю алгоритм сначала. И так пока что-то на поле меняется. TL6.
Подскажите, пожалуйста, что не так, может быть есть другая идея решения?

Решение:

#include <cstdio>
#include <memory.h>

const int maxl = 1001;

char s[maxl][maxl];
int n, m, u[maxl][maxl];
int xl, yl, xr, yr;

int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[8] = {0, 1, 0, -1, -1, 1, 1, -1};
int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};

void walk(int x, int y)
{
  if (x < 0 || y < 0 || x >= n || y >= m)
    return;
  if (s[x][y] != '.')
    return;
  if (u[x][y])
    return;
  u[x][y] = 1;
  if (x < xl)
    xl = x;
  if (y < yl)
    yl = y;
  if (x > xr)
    xr = x;
  if (y > yr)
    yr = y;
  for (int i = 0; i < 8; i++)
    walk(x + dx[i], y + dy[i]);
}

int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++)
    scanf("%s", s[i]);
  
  memset(u, 0, sizeof(u));
  
  bool anychanged = true;
  
  while (anychanged) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        if (s[i][j] == 'X' && !u[i][j]) {
	  xl = i, xr = i;
          yl = j, yr = j;
	
	  walk(i, j);
	
	  for (int x = xl; x <= xr; x++)
	    for (int y = yl; y <= yr; y++)
	      s[x][y] = 'X', u[x][y] = 1;
        }
    
    anychanged = false;
    
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
	if (s[i][j] == '.') {
	  int c = 0;
	  for (int k = 0; k < 4; k++)
	    if (i + di[k] >= 0 && j + dj[k] >= 0 && i + di[k] < n && j + dj[k] < m && s[i + di[k]][j + dj[k]] == 'X')
	      ++c;
	  if (c >= 2)
	    s[i][j] = 'X', anychanged = true;
	}
  }
  
  int c = 0; 
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      c += (s[i][j] == 'X');
      
  printf("%d\n", c);
  return 0;
}

[lordKelvin]

Можно по такому принципу довести систему до стабильного состояния, но мы по-прежнему в крайних случаях (1000 x 1000) не укладываемся в отведенную память, даже если будем хранить участок, используя битовые маски.

#define SIDE 10
#define FULL_SIDE (SIDE+2)

void grow( char field[ FULL_SIDE ][ FULL_SIDE ] )
{
    bool changed;
    do
    {
        changed = false;
        memset( field[ 0 ], '.', FULL_SIDE );
        for( int y = 1; y <= SIDE; y++ )
        {
            for( int x = 1; x <= SIDE; x++ )
            {
                int S = field[ 0 ][ x ];
                if( ( field[ 0 ][ x ] = field[ y ][ x ] ) == '.' )
                    if( S + field[ y + 1 ][ x ] + field[ y ][ x + 1 ] +
                        field[ 0 ][ x - 1 ] > 'X' + '.' * 3 )
                            field[ y ][ x ] = 'X', changed = true;
            }
        }
    } while( changed );
}