1 Тема от temp1 Отредактировано temp1 (15.11.2006 09:31:35)

  • temp1
  • горец почечуйный
  • Неактивен
  • Откуда: QRDL
  • Зарегистрирован: 09.06.2005
  • Сообщений: 7,102

есть поле MxN кнопок, кнопки могут быть двух цветов, чёрные и белые
при нажатии на кнопку она меняет цвет на противоположный, так же цвет на противоположный меняют граничащие с ней по ребру кнопки
если полез иначально чёрное, существует ли общий алгоритм по которому можно всё поле инверсировать?

какие ограничения на M и N?

естественно несколько кнопок одновременно нажать нельзя

Сайтtemp1

2 Ответ от Ivanes$

  • Ivanes$
  • кактус
  • Неактивен
  • Откуда: ivaness.ru
  • Зарегистрирован: 29.07.2005
  • Сообщений: 4,879

Кажется, нигда не сказано, что кнопки можно нажимать только по одной?.. default/smile)

СайтIvanes$

3 Ответ от Механик Отредактировано Механик (15.11.2006 09:34:21)

  • Зарегистрирован: 19.01.2006
  • Сообщений: 20,854

Блять... Почитал условие задачки и первое, что пришло в голову - это запустить под виндами  игру "минёр"...
Теперь кажись понял чо такое "уровень апстрактного интеллекта

4 Ответ от temp1

  • temp1
  • горец почечуйный
  • Неактивен
  • Откуда: QRDL
  • Зарегистрирован: 09.06.2005
  • Сообщений: 7,102
Ivanes$ пишет:

Кажется, нигда не сказано, что кнопки можно нажимать только по одной?.. default/smile)

две одновременно не нажимаются

Сайтtemp1

5 Ответ от Ivanes$

  • Ivanes$
  • кактус
  • Неактивен
  • Откуда: ivaness.ru
  • Зарегистрирован: 29.07.2005
  • Сообщений: 4,879
temp3 пишет:
Ivanes$ пишет:

Кажется, нигда не сказано, что кнопки можно нажимать только по одной?.. default/smile)

две одновременно не нажимаются

Ну, значит опустить на поле бетонную плиту не подходит. default/smile

СайтIvanes$

6 Ответ от srez

  • srez
  • Светоч
  • Неактивен
  • Откуда: Спб
  • Зарегистрирован: 01.07.2005
  • Сообщений: 9,775
Ivanes$ пишет:
temp3 пишет:
Ivanes$ пишет:

Кажется, нигда не сказано, что кнопки можно нажимать только по одной?.. default/smile)

две одновременно не нажимаются

Ну, значит опустить на поле бетонную плиту не подходит. default/smile

*)))
Вообще для поля 2*1, очевидно задача решается в 1 ход.
Для поля 1*1 тоже.
Для поля 2*2 в принципе тоже решается в 4 хода.

Сайтsrez

7 Ответ от Ёп!жик

  • Ёп!жик
  • душица серая
  • Неактивен
  • Откуда: Москва
  • Зарегистрирован: 06.09.2005
  • Сообщений: 3,773

M не равно N?
*умный ты, Темп, аж жутко становится*

СайтЁп!жик

8 Ответ от masai

  • masai
  • душица серая
  • Неактивен
  • Зарегистрирован: 12.06.2005
  • Сообщений: 3,544

Я тут подумал, вроде существует общий алгоритм без ограничений. Щас нарисую картинку и запощу.

9 Ответ от Noire

  • Noire
  • горец почечуйный
  • Неактивен
  • Откуда: Ukraine
  • Зарегистрирован: 09.06.2005
  • Сообщений: 7,007

Сколько кнопок граничит с одной кнопкой. Можно уточнить? При условии, что кнопка не с краю поля.

СайтNoire

10 Ответ от srez

  • srez
  • Светоч
  • Неактивен
  • Откуда: Спб
  • Зарегистрирован: 01.07.2005
  • Сообщений: 9,775

3*1 тоже решается в 1 ход, продолжаю исследования 8)))

Сайтsrez

11 Ответ от srez

  • srez
  • Светоч
  • Неактивен
  • Откуда: Спб
  • Зарегистрирован: 01.07.2005
  • Сообщений: 9,775
Noire пишет:

Сколько кнопок граничит с одной кнопкой. Можно уточнить? При условии, что кнопка не с краю поля.

по ребру граничит 4 кнопки очевидно. для угловых 2, для граничных - 3.

Сайтsrez

12 Ответ от Механик

  • Зарегистрирован: 19.01.2006
  • Сообщений: 20,854
masai пишет:

Я тут подумал, вроде существует общий алгоритм без ограничений. Щас нарисую картинку и запощу.

А не проще запустить "минёра"? Ткнуть пару-тройку раз в кнопки и алгоритм станет ясным

13 Ответ от Noire

  • Noire
  • горец почечуйный
  • Неактивен
  • Откуда: Ukraine
  • Зарегистрирован: 09.06.2005
  • Сообщений: 7,007

Механик, во-первых в минере несколько другая задачка, во-вторых очевидно что аффтору нужен формализованный алгоритм.

СайтNoire

14 Ответ от ёлка

  • ёлка
  • красавка обыкновенная
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 02.12.2005
  • Сообщений: 1,654
srez пишет:
Noire пишет:

Сколько кнопок граничит с одной кнопкой. Можно уточнить? При условии, что кнопка не с краю поля.

по ребру граничит 4 кнопки очевидно. для угловых 2, для граничных - 3.

очевидно это только если кнопки четырёхугольные. для шестиугольных будет 6 default/smile

Сайтёлка

15 Ответ от srez

  • srez
  • Светоч
  • Неактивен
  • Откуда: Спб
  • Зарегистрирован: 01.07.2005
  • Сообщений: 9,775
ёлка пишет:
srez пишет:
Noire пишет:

Сколько кнопок граничит с одной кнопкой. Можно уточнить? При условии, что кнопка не с краю поля.

по ребру граничит 4 кнопки очевидно. для угловых 2, для граничных - 3.

очевидно это только если кнопки четырёхугольные. для шестиугольных будет 6 default/smile

А для круглых ваще нет граничащих по ребру. 8)

Сайтsrez

16 Ответ от Механик

  • Зарегистрирован: 19.01.2006
  • Сообщений: 20,854
Noire пишет:

Механик, во-первых в минере несколько другая задачка, во-вторых очевидно что аффтору нужен формализованный алгоритм.

Ага. Другая.
Тем не менее не трудно уразуметь каков будет алгоритм решения этой "олимпиадной задачи".А уразумев - попробовать формализовать...

17 Ответ от ёлка

  • ёлка
  • красавка обыкновенная
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 02.12.2005
  • Сообщений: 1,654
srez пишет:
ёлка пишет:
srez пишет:

по ребру граничит 4 кнопки очевидно. для угловых 2, для граничных - 3.

очевидно это только если кнопки четырёхугольные. для шестиугольных будет 6 default/smile

А для круглых ваще нет граничащих по ребру. 8)

ну, раз говорилось о граничащих по ребру - можно предположить, что наличие рёбер подразумевалось. а вот об их количестве не сказали ничего

Сайтёлка

18 Ответ от temp1

  • temp1
  • горец почечуйный
  • Неактивен
  • Откуда: QRDL
  • Зарегистрирован: 09.06.2005
  • Сообщений: 7,102
Noire пишет:

Сколько кнопок граничит с одной кнопкой. Можно уточнить? При условии, что кнопка не с краю поля.

кнопка квадратная, граничат по ребру
соответсвенно для угловых - двое соседей
для крайних - трое
для остальных - четверо

Сайтtemp1

19 Ответ от Noire

  • Noire
  • горец почечуйный
  • Неактивен
  • Откуда: Ukraine
  • Зарегистрирован: 09.06.2005
  • Сообщений: 7,007
ёлка пишет:
srez пишет:
ёлка пишет:

очевидно это только если кнопки четырёхугольные. для шестиугольных будет 6 default/smile

А для круглых ваще нет граничащих по ребру. 8)

ну, раз говорилось о граничащих по ребру - можно предположить, что наличие рёбер подразумевалось. а вот об их количестве не сказали ничего

Именно это я и имела ввиду :-)

СайтNoire

20 Ответ от masai

  • masai
  • душица серая
  • Неактивен
  • Зарегистрирован: 12.06.2005
  • Сообщений: 3,544
srez пишет:

3*1 тоже решается в 1 ход, продолжаю исследования 8)))

Вообще решаются 1xN, 2xN, 3xN, 4xN.