Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.12.2008, 17:10
Новичок

Отправить личное сообщение для irvind Посмотреть профиль Найти все сообщения от irvind
 
Регистрация: 28.12.2008
Сообщений: 2

[игра][lines] проверка возможности хода
Здравствуйте.

Делаю свою реализацию игры Lines (наверно, многие играли: нужно по полю двигать шарики, чтобы лиинию из 5 шариков получить, чтобы их убрать, а этих шариков тем временем становится больше). Столкнулся с препятствием:

Нужно осуществить проверку правильности/возможности хода:

вот тут ход в нужную область возможен


а тут нет.

Вобщем, с помощью какого алгоритма это можно сделать?

Заранее спасибо.
  #2  
Старый 28.12.2008, 17:51
гость

 
Сообщений: n/a

Для тех кто не играл, разъясните критерий допустимости хода

Из вашего рисунка, я так понимаю, нужно всего лишь проверить, можно ли из клетки A добраться в клетку B двигаясь влево/вправо/вверх/вниз? Если так, то например самый простой алгоритм - поиск в глубину.
  #3  
Старый 28.12.2008, 19:47
Новичок

Отправить личное сообщение для irvind Посмотреть профиль Найти все сообщения от irvind
 
Регистрация: 28.12.2008
Сообщений: 2

Сообщение от гость Посмотреть сообщение
Из вашего рисунка, я так понимаю, нужно всего лишь проверить, можно ли из клетки A добраться в клетку B двигаясь влево/вправо/вверх/вниз? Если так, то например самый простой алгоритм - поиск в глубину.

Да это именно так.

Я как понял алгоритм поиска в глубину основан на графах. А существует ли решение без использования графов? Просто с графами я незнаком и у меня уйдет некоторое временя на знакомство с ними.

Последний раз редактировалось irvind, 28.12.2008 в 19:50.
  #4  
Старый 28.12.2008, 20:18
гость

 
Сообщений: n/a

Да тут ничего сложного нет. Вот как я бы реализовал это на C:

Код:
int visited[ROWS+2][COLS+2];
int free_cell[ROWS+2][COLS+2];

void dfs(int y, int x) {
  if (free_cell[y][x] && !visited[y][x]) {
    visited[y][x] = 1;
    dfs(y-1, x);
    dfs(y+1, x);
    dfs(y, x-1);
    dfs(y, x+1);
  }
}

int main() {
  ...
  memset(visited, 0, sizeof(visited));
  memset(free_cell, 0, sizeof(free_cell));

  for (int y = 1; y <= ROWS; y++)
    for (int x = 1; x <= COLS; x++)
      free_cell[y][x] = <является ли клетка (y, x) свободной>;

  dfs(y0, x0);  // (y0, x0) - координаты клетки начала движения

  теперь для всех клеток которые достижимы из (y0, x0), имеем: visited[y0][x0] = 1.
  #5  
Старый 28.12.2008, 20:20
гость

 
Сообщений: n/a

Сообщение от irvind Посмотреть сообщение
А существует ли решение без использования графов?
Маловероятно.
  #6  
Старый 12.04.2010, 14:45
гость

 
Сообщений: n/a

Исходники
Вот, посмотрите здесь: http://softmind.bos.ru/source/prod_smlines.shtml
Может поможет.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Игра Пятнашки Kichx Математические алгоритмы (другое) 6 22.11.2010 06:42
игра Белла Решение задач с acm.sgu.ru 5 19.11.2009 09:50
Игра Сима shornik Реализация, исходники, языки 5 03.11.2008 15:05
игра Белла Задачи 1 16.04.2008 22:10
игра незарегистрированный Задачи 3 05.05.2007 13:10