Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
andymitrich
0 / 0 / 0
Регистрация: 26.12.2014
Сообщений: 3
1

Поиск максимального паросочетания в задаче "Испорченный паркет"

26.12.2014, 09:48. Просмотров 807. Ответов 4
Метки нет (Все метки)

Привет всем! Прошу помощи.

Есть задача "Испорченный паркет". Условие задачи следующее:

Пол в некоторой комнате размером M ×N замощен паркетом. При этом некоторые плитки паркета оказались испорчены. Петя решил сделать ремонт в этой комнате, заменив только испорченные клетки. Придя в магазин, он обнаружил, что паркетные плитки бывают двух типов - размера 1 × 2, которые стоят A рублей (немного подумав, Петя понял, что плитки 1×2 можно поворачивать на 90 градусов, получая тем самым плитки 2×1) и размера 1 × 1, которые стоят B рублей. Разрезать плитку размера 1 × 2 на две, размера 1 × 1 Петя не может. Определите, какая минимальная сумма денег нужна Пете, чтобы сделать ремонт.

Формат ввода
Первая строка входных данных содержит 4 целых числа N, M, A, B (1 ≤ N, M ≤ 300, A, B ≤ 1000). Каждая из последующих N строк содержит по M символов. Символ «.» обозначает неиспорченную плитку паркета, а символ «*» — испорченную. В конце строк могут идти незначащие пробелы. В конце входных данных могут быть пустые строки.

Формат вывода
В выходных данных выведите одно число — минимальную сумму денег, которую необходимо будет потратить для ремонта в комнате.

Решение
Для решения я использовал алгоритм Куна для нахождения максимального паросочетания в двудольном графе: если раскрасить плитки паркета в "шахматы", то получается, что в двойной плитке (размера 1х2) одна плитка лежит на белой стороне, другая - на черной. Таким образом, испорченные плитки, которые находятся рядом можно соединить ребрами и получить двудольный граф.

Решение я написал, но оно проходит только 11 тестов, на 12-ом валится. Очевидный ответ давать не прошу. Если кто-нибудь может привести пример теста, на котором свалится решение, или направить меня в нужном направлении - помогите

Код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector> 
#include <cstdio>
#include <list>
#include <map>
 
std::vector<int> mt;
std::vector<char> marked;
 
 
bool visit(int vertex, std::list<int> adj) {
    if (marked[vertex]) {
        return false;
    }
 
    marked[vertex] = true;
    
    std::list<int>::iterator it;
    for (it = adj.begin(); it != adj.end(); ++it) {
        if (mt[*it] == -1) {
            mt[*it] = vertex;
            return true;
        }
    }
 
    return false;
}
 
 
int pos(int row, int column, int cols) {
    return row * cols + column;
}
 
 
int main() {
    int rows, cols, aPrice, bPrice;
    int count = 0, flow = 0;
    char ch;
    std::map <int, std::list <int> > adjacency;
    std::vector < std::vector<char> > matrix;
    
    std::cin >> rows >> cols >> aPrice >> bPrice;
    matrix.reserve(rows);
 
    int position, current;
    bool isBlack;
 
    for (int iindex = 0; iindex < rows; ++iindex) {
        for (int jindex = 0; jindex < cols; ++jindex) {
            std::cin >> ch;
            matrix[iindex].push_back(ch);
 
            if (ch == '*') {
                current = pos(iindex, jindex, cols);
                isBlack = (iindex % 2 == 0) ? (jindex % 2 == 0) : (jindex % 2 == 1);
                count++;
 
                if (jindex > 0 && matrix[iindex][jindex-1] == '*') {
                    if (isBlack)
                    {
                        position = pos(iindex, jindex - 1, cols);
                        adjacency[position].push_back(current);
                    }
                    else
                    {
                        position = pos(iindex, jindex - 1, cols);
                        adjacency[current].push_back(position);
                    }
                }
 
                if (iindex > 0 && matrix[iindex-1][jindex] == '*') {
                    if (isBlack)
                    {
                        position = pos(iindex - 1, jindex, cols);
                        adjacency[position].push_back(current);
                    }
                    else
                    {
                        position = pos(iindex - 1, jindex, cols);
                        adjacency[current].push_back(position);
                    }
                }                
            }
        }
    }
 
    if (2 * bPrice <= aPrice) {
        std::cout << count * bPrice;
        return 0;
    }
 
    int vertices = rows * cols;
    mt.assign(vertices, -1);
 
    for (auto outer = adjacency.begin(); outer != adjacency.end(); ++outer) {
        marked.assign(vertices, false);
 
        if (visit(outer->first, outer->second)) {
            flow++;
        }
    }
    
    int total = aPrice * (flow) + (count - 2 * flow) * bPrice;
    std::cout << total;
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2014, 09:48
Ответы с готовыми решениями:

Поиск максимального элемента в массиве методом "разделяй и властвуй"
Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его...

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")
Добрый день Имею такое задание: необходимо написать программу, которая сможет найти в файле...

Поиск частей внешнего контура по четырём сторонам с "захватом"
Вот так вот чудно я назвал тему =) Всем привет. В рамках проекта нужно придумать алгоритм поиска...

Поиск алгоритма перемещения стопки карт в "Свободной ячейке"
Добрый день, друзья. Споткнулись на поиске алгоритма определения последовательности перемещения...

Как работает метод ОПГ надстройки "Поиск решения" Excel
Как работает метод ОПГ (&quot;Метод обобщенного градиента&quot;) надстройки &quot;Поиск решения&quot; Excel? Есть ли...

4
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
26.12.2014, 10:37 2
Код не смотрел. Есть предположение, что задача не запрещает заменять целые плитки.

Попробуй такие 4 теста, я думаю, что правильные ответы 10 5 5 15:
Код
1 1 5 10
*

1 2 5 10
.*

1 3 5 10
.*.

1 3 5 10
***
0
andymitrich
0 / 0 / 0
Регистрация: 26.12.2014
Сообщений: 3
26.12.2014, 10:46  [ТС] 3
@Qwertiy Да вроде нельзя так. В условии указано, что "Петя решил сделать ремонт в этой комнате, заменив только испорченные клетки".
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
26.12.2014, 11:14 4
Так.. А другой случай, когда двойная плитка стоит дороже двух одинарных, ты предусмотрел?
Код
1 2 100 3
**
0
andymitrich
0 / 0 / 0
Регистрация: 26.12.2014
Сообщений: 3
26.12.2014, 11:33  [ТС] 5
Цитата Сообщение от Qwertiy Посмотреть сообщение
Так.. А другой случай, когда двойная плитка стоит дороже двух одинарных, ты предусмотрел?
Код
1 2 100 3
**
Да, конечно.
0
26.12.2014, 11:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.12.2014, 11:33

Граф, поиск "критического" узла (java)
критический - если мы его уберем, то любые 2 или больше узлов бутут разорваны (тоесть узел через...

"Задача на поиск чего-либо в массиве"
Представим ситуацию, что надо, например, проверить массив на наличие в нем, например, цифры 5....

Поиск пути на графе — "муравьед"
Привет Необходимо реализовать этот алгоритм. Язык не важен, исходные данные пока не важны. Суть...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru