Не указаны ограничения, поэтому нельзя точно сказать, что это решение будет самым быстрым, но скорее всего задача решается через
паросочетание на двудольном графе.
Покрасьте поле как шахматную доску. Черные и белые клетки. Каждая доминошка будет лежать на двух соседних белой и черной клетках. Постройте граф. Назначьте каждой клетке вершину, а ребра проведите между соседними клетками, если там нет перегородки. Граф - двудольный, ведь черные клетки окружены белыми, а белые - черными. Любое заполнение поля доминошками будет идентично паросочетанию в этом графе и наоборт. Найдите максимальное паросочетание: если оно не полное, то поле покрыть нельзя. Иначе ребра в паросочетании будут местами, куда надо класть доминошки.
Вот статья с описанием алгоритма и реализацией.
Это будет решение за O(n^2m^2).
Другое решение, которое будет быстрее, если одно из измерений очень маленькое, а второе очень большое - динамическое программирование по профилю. Гуглите эти слова. Это сложнее реализовать, но зато будет работать за O(4^n m)
Edit:
Alexandroppolus в коментариях предложил использовать
Алгоритм Хопкрофта — Карпа для поиска паросочетания, что для данного графа будет быстрее предложенного мной алгоритма Куна и будет работать за O(nm sqrt(nm)) вместо O(n^2 m^2)
