Как декодировать матрицу?

Question

[Xiran]

В общем есть задача указать, какой способ кодирования был применен к условной матрице.
Способы кодирования, каждый элемент матрицы заменяется на:
1. Сумму соседних по стороне элементов матрицы включая его самого.

Пример

1 2
3 4
кодируется в
6 7
8 9

2. Сумму соседних элементов и по стороне, и по углу, не включая его самого.

Пример

1 2
3 4
кодируется в
9 8
7 6

3. Сумму соседних элементов только по стороне, не включая его самого.

Пример

1 2
3 4
кодируется в
5 5
5 5

Насколько я понял, надо написать функцию, которая возвращает все возможные вектора слагаемых из k элементов, которые являются суммой числа n.
Вместо тысячи слов ее сигнатура:

std::vector<std::vector<int>> split_int(int n, int k);

И для каждого элемента матрицы нужно каким-то образом подобрать вектор слагаемых, что-бы все совпало.
Вопрос в том, правильно ли я думаю, реализуемо ли это?

Comments

[mayton2019]

Никто не знает о чем ты думаешь. Напиши код. Тогда можно обсудить код.

[Wataru]

Странное условие. Сформулируйте четко, что дано, что надо получить на выходе. С примерами.

Так-то, матрицу
6 6
6 6

Можно получить из суммой по сторонам из
6 6
0 0

суммой по сторонам с самим элементом из:
2 2
2 2

суммой по сторонам и углам из:
2 2
2 2

Только по самой матрице не всегда можно определить, а каким же способом она была получена.

[Xiran]

Wataru, вот матрица:
2 15 4 13
15 11 28 8
8 19 14 18
P.S. исходные элементы в диапазоне 1-9. Может, можно было бы просто перебрать, но я боюсь, что будет медленно.

[Xiran]

И к ф-ции нужно было добавить верхнюю границу слагаемого

[Xiran]

Wataru, примеров нет, есть таблица расшифровки и даже ответ
о д а р к б щ н и
1 2 3 4 5 6 7 8 9
корообдирщик

[Xiran]

Но нужно решить самому

[Wataru]

Xiran, Так, уже лучше. На исходную матрицу ограничения: целые число от 1 до 9. При чем там буквы и "корообдирщик"? Это задача заменить буквы на цифры, чтобы арифметическое выражение выполнялось? И вы как-то свели ее к матрице и таким преобразованиям?

[Xiran]

Wataru, сначала по таблице из слова формируется исходная матрица, потом шифруется одним из 3 способов, нужно подобрать каким, а потом декодировать по таблице.

[Wataru]

Xiran, Нет, все еще формулировка ужасная. Итак, правильно ли я понял:
Была матрица из букв, потом по известной вам таблице буквы преобразовали в цифры, потом одним из трех способов преобразовали сложив соседей (вам неизвестно каким) и результат дали вам - надо восстановить исходные буквы?

[Xiran]

Wataru, да

[Wataru]

Xiran, Какие еще ограничения есть? Размер матрицы какой может быть?

[Xiran]

Wataru, никаких, размер такой же

[Wataru]

Xiran, Нет же. Вам надо, чтобы ваше решение работало на матрице размера до 1000x1000? Или вам дана одна конкретная матрица, скажем, 3x5. Или где-то сказано, что всего в искомом слове может быть до 20 букв?

[Xiran]

Wataru, да, это не пример, это конкретная задача, ее можно хоть на листочке решить

[Xiran]

Извините за условие, мне можно было сразу все уточнить

Answer 1

[Wataru]

В комментариях мы выяснили, что была матрица 3x4 из цифр от 1 до 9. над ней произвели одно из трех действий и выдали результат. Надо по нему восстановить исходную матрицу. Надо решить на одной конкретной матрице.

Надо попробовать применить все 3 метода и посмотреть, какой из них даст матрицу из цифр 1-9.

Итак, для случаев "стороны включая элемент" и "стороны не включая элемент" можно восстановить исходную матрицу однозначно перебрав только первый столбец. Потому что посмотрите на любое число в первом столбце. Вы знаете изначальное число там (вы его перебрали) и знаете сумму известных чисел в столбце и числа справа (это вам дано в матрице). Отсюда можно найти число справа. Когда вы восстановили второй столбец, пройдитесь по всем клеткам в нем и из уравнений для значений там восстановите третий столбец и т.д.

Вот так проделайте для 9^3 вариантов, если по пути получили числа не из диапазона 1-9, то можно дальше не считать, надо пробовать другой вариант для первого столбца.

Чуть хуже для случая "стороны и диагонали не включая элемент". Все так же переберите 3 числа в первом столбце. Во втором столбце вы получаете 3 уравнения: сумма первых двух чисел известна из числа в первой строке. Сумма всех трех известна из числа для второй строки. Сумма двух последних - из последнего числа. Т.е. вам дано x+y=A, x+y+z=B, y+z=C. Отсюда элементарно z=B-A, x=B-C, y=A+C-B.

Этот перебор отработает где-то за 1мс - довольно быстро.

Есть более общий метод. У вас есть матрица из неизвестных, а каждое число в заданной матрице - это правая часть линейного уравнения. Вот составьте матрицу - выпишите эти все линейные уравнения. Методом Гаусса ее преобразуйте в диагональный вид. Какие-то переменные станут свободными - их надо перебрать. Оставшиеся по известным уравнениям посчитать.