воскресенье, 13 ноября 2011 г.

Задача: Путь в двумерном массиве


Добрый вечер, уважаемые читатели.
Сегодня вам предлагается решить ниже следующую задачу. (предыдущие задачи тут и тут.
Свои решения можно публиковать здесь или присылать по адресу:kazanqacomm@gmail.com (с пометкой Лабиринт)
А через месяц мы подведем итоги, и отметим самые удачные идеи.






Итак условия:

Программист написал программу, которая принимает на вход текстовый файл в, котором содержиться массив нулей и единиц, размером 10х10. Ниже пример такого массива:

0, 0, 1, 0, 0, 0, 0, 0, 0, 0
1, 0, 0, 0, 0, 1, 0, 0, 1, 0
0, 0, 0, 1, 1, 1, 0, 0, 1, 1
0, 1, 0, 0, 0, 1, 0, 0, 1, 0
0, 0, 0, 0, 1, 1, 1, 0, 1, 0
0, 0, 1, 1, 1, 0, 1, 0, 0, 0
0, 0, 0, 1, 0, 0, 1, 0, 0, 0
1, 1, 0, 1, 0, 0, 1, 1, 1, 0
0, 1, 0, 0, 0, 0, 1, 0, 0, 0
0, 1, 0, 0, 0, 0, 1, 0, 0, 0

Получается лабиринт, где 1 - это стена, 0 - это свободный путь. Вход в лабиринт - левый верхний угол (координата - [0;0], а выход - правый нижний (координата - [9;9])
Программа, анализирует массив и выдает два значения:
true - если выход из массива существует
false - если выхода не существует.
По какому алгоритму реализована задача мы не знаем.

Тестировщики, какие бы вы тесты придумали для этой программы? Ждем ваших тестов.

6 комментариев:

  1. white-box testing в помощь!
    Для приёмочного тестирования достаточно будет 3-4 сложных примера входных массивов типа:

    0 0 1 0 0 0 1 0 0 0
    1 0 1 0 1 0 1 0 1 0
    1 0 0 0 1 0 0 0 1 0
    0 1 1 1 0 1 1 1 0 0
    0 0 0 0 0 0 0 1 0 1
    0 0 0 1 1 1 0 0 0 0
    1 0 1 0 0 0 1 1 1 0
    0 0 1 1 1 0 0 0 0 0
    0 1 0 0 0 1 1 1 1 1
    0 0 0 1 0 0 0 0 0 0

    ОтветитьУдалить
  2. Вспомнил историю про парня, попавшего на школьную олимпиаду по программированию, на которой было задание, схожее с этим. Нужно было определить наличие выхода из лабиринта, составленного по тому же методу. Ввиду нежелания писать сложный код, он сделал следующее: он визуализировал эту матрицу, представив каждый её элемент как квадрат 1х1, который закрашен или не закрашен цветом в зависимости от того стена там или нет. Ну и потом делал заливку начиная от квадрата предполагаемого входа и проверял её наличие в квадрате предполагаемого выхода. Решение было признано самым оригинальным :)

    Вот, а в случае тестирования естественно проверяем наличие входа и выхода, то есть то, что квадраты [0,0] и [9,9] -нули. А остальное - чистая проверка функционала. Как товарищ выше написал - или анализировать код, или подсунуть несколько примеров с уже известным ответом.

    ОтветитьУдалить
  3. Такой вот набросок:

    Тест1: все нули
    Тест2: все единицы (или просто 0x0 = 1)
    Тест3: все крайние элементы по периметру нули - все внутренние единицы
    Тест4: все нули кроме 9X9
    Тест5: все единицы кроме 9x9
    Тест6: вход = 0, выход =0 , свободного пути между ними нет
    Тест7: вход = 0, выход =0 , есть несколько свбодных путей (но есть и единицы )

    ОтветитьУдалить
  4. Добавлю еще:
    задать матрицу, не содержащую выхода, но содержащую кольцо нулей, из которого выйти можно только обратно ко входу

    ОтветитьУдалить
  5. 1) Подсунуть матрицу 1000 на 1000, в которой еще и мусор напихать
    2) Подсунуть файл большого размера, испорченный файл и т.д.
    3) Ну и развивая крайней каммент- попытаться написать такую матрицу, что бы зациклить программу

    ОтветитьУдалить
  6. 2shaddy-очень похоже на волновой метод, который является самым оптимальным.

    ОтветитьУдалить