1 Тема от kesha

  • kesha
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-09
  • Сообщений: 17

Тема: SGU 344 - Weed

WA5. Мое решение - пробегаю несколько раз по полю и заменяю незанятые клетки с числом соседей >= 2 на занятые.
Подскажите, пожалуйста, что может быть не так.

#include <cstdio>

const int maxl = 1001;

char s[maxl][maxl];
int n, m;

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

int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++)
    scanf("%s", s[i]);
  for (int c = 0; c < 10; c++) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) {
    int c = 0;
    for (int k = 0; k < 4; k++)
      if (i + di[k] >= 0 && i + di[k] < n && j + dj[k] >= 0 && j + dj[k] < m && s[i + di[k]][j + dj[k]] == 'X')
        ++c;
    if (c >= 2)
      s[i][j] = 'X';
      }
  }
  int c = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (s[i][j] == 'X')
    ++c;
  printf("%d\n", c);
  return 0;
}

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: SGU 344 - Weed

А почему вы уверены что через 10 итераций заполнение прекратится?

.....X
....X.
...X..
..X...
.X....
X.....

На таком тесте ответ порядка N, т.е. если взять таблицу побольше, то за 10 итераций заполнение еще не успеет закончиться. Отсюда и ВА.

3 Ответ от kesha

  • kesha
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-09
  • Сообщений: 17

Re: SGU 344 - Weed

Мне кажется, что в таком случае TL будет. Может быть есть более адекватное решение?

4 Ответ от kesha

  • kesha
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-09
  • Сообщений: 17

Re: SGU 344 - Weed

Ага, если каждый раз смотреть, изменилось ли что-то и пробегать по полю, пока что-то меняется (заполняются новые клетки), то получается TL6

5 Ответ от kesha

  • kesha
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-09
  • Сообщений: 17

Re: SGU 344 - Weed

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

WA4 (

#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 (u[x][y])
    return;
  u[x][y] = 1;
  if (x < xl && y < yl)
    xl = x, yl = y;
  if (x > xr && y > yr)
    xr = x, 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[y][x] = 'X', u[y][x] = 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;
}