Основная часть. Для решения поставленной задачи была создана рекурсивная функция step

Для решения поставленной задачи была создана рекурсивная функция step, которая отвечает за прохождение комнат замка и отмечает посещенные клетки.

void step(int a[N][N], int b, int c, int d)

{...}

Разберем, что же происходит в теле функции. Для начала помечаем клетку, если до этого мы в ней не были.

if (a[b][c]<=15) a[b][c] = a[b][c] + 100 * d;

Далее проверяем не отделена ли правая клетка стенкой и вызываем функцию step от нее.

if (a[b][c + 1] == 2 || a[b][c + 1] == 4 || a[b][c + 1] == 6 || a[b][c + 1] == 8 ||

a[b][c + 1] == 10 || a[b][c + 1] == 12 || a[b][c + 1] == 14 || a[b][c + 1] == 0)

{ step(a, b, c + 1, d); }

И так для всех четырех соседних клеток соответственно. Таким образом, обойдем все клетки в комнате. На этом рекурсия сворачивается.

В основной части программы для начала подключаемся к файлу input.txt и считываем данные из него.

FILE *file;

fopen_s(&file,"input.txt", "r");

fscanf_s(file, "%d", &n);

fscanf_s(file, "%d", &m);

for (int i = 0; i < n; i++)

{ for (int j = 0; j < m; j++)

fscanf_s(file, "%d", &arr[i][j]); }

fclose(file);

Далее идем по массиву, пока не найдем не посещенную клетку, и запускаем функцию step. Для этого был создан счетчик с, отвечающий за номер комнаты.

for (i = 0; i < n; i++)

{ for (j = 0; j < m; j++)

{ if (arr[i][j] <= 15)

{ c++;

step(arr, i, j, (c));

}

}

}

Для выполнения второго задания, задействован массив b, в котором находится информация о количестве клеток в комнате. b[0] соответствует интервал от 15 до 115, для b[1] от 115 до 215 и так далее, таким образом, при вхождении числа в клетке массива его значение увеличивается на единицу. При полном заполнении массива b, идет нахождение наибольшего элемента массива, который отвечает за площадь комнаты.

for (k = 1; k!= c + 1; k++)

{ for (i = 0; i < n; i++)

{ for (j = 0; j < m; j++)

{ s = (k - 1) * 100 + 15;

s2 = 100 * k + 15;

if (arr[i][j] > s && arr[i][j] <= s2) q++;

}

}

b[k - 1] = q;

q = 0;

}

q = 0;

for (k = 0; k!= c; k++)

{ if (q < b[k]) q = b[k]; }

Для того чтобы удалить стенку, снова пробегаем массив и сравниваем клетку, в которой находится программа и клетку расположенную справа или снизу, смотреть клетки выше или левее нет смысла, так как это будет та же самая стенка, что была найдена ранее. Чтобы сравнить элементы массива arr мы делим значение элемента массива на сто нацело. Кроме того используется переменная k, которая отвечает за наибольшую площадь комнаты при удалении стенки и если эта сумма будет меньше, чем суммы других двух комнат, то k принимает значение суммы этих комнат, и при этом запоминаются значения столбца и строки в которой нужно удалить стенку, а дополнительной переменной присваивается значение 69 или 83, при распечатке которых символами будет выводиться на экране E или S соответственно. Для получения суммы из которой получается значение k, мы элементы массива arr делим на сто нацело и вычитаем единицу для нахождения номера слагаемого, находящегося в массиве b. Стоит отметить, что программа будет учитывать только первое удаление стены, остальные же удаления учитываться не будут.

for (i = 0; i < n - 1; i++)

{ for (j = 0; j < m - 1; j++)

{ if (arr[i][j] / 100!= arr[i + 1][j] / 100 && k < b[(arr[i][j] / 100) - 1] + b[(arr[i + 1][j] / 100) - 1])

{ k = b[(arr[i][j] / 100) - 1] + b[(arr[i + 1][j] / 100) - 1]; s = i; s2 = j; r = 83;

}

if (arr[i][j] / 100!= arr[i][j + 1] / 100 && k < b[(arr[i][j] / 100) - 1] + b[(arr[i][j + 1] / 100) - 1])

{ k = b[(arr[i][j] / 100) - 1] + b[(arr[i][j + 1] / 100) - 1]; s = i; s2 = j; r = 69;

}

}

При выполнении задания возникли следующие проблемы:

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

· пометка клеток, в которых программа находилась несколько раз. Данная ошибка была исправлена постановкой условия в начале рекурсии: пометка клетки происходит только в том случае, если она не была помечена ранее, то есть число в клетке должно быть хотя бы менее 100.

Дата добавления: 2015-08-20