Решение задачи Шахматная мастерская с Acmp

С пояснением   Просмотров: 45


Хозяин мастерской по изготовлению шахматных досок гроссмейстер Хосе Раулевич Капабланка был очень зол. «Ну, кто так раскрашивает доски?! Ну скажи мне, Бобби, разве я тебя так учил раскрашивать доски?!» - спрашивал он у своего подмастерья.

А дело было вот в чем. Недавно его мастерская получила заказ на изготовление нестандартной шахматной доски размером N на M . Саму шахматную доску из дорогой породы дерева он изготовил, а раскрасить ее поля он поручил своему подмастерью и ученику Бобби. Бобби, однако, справился с этой задачей очень плохо. Он раскрасил доску так, что некоторые соседние поля оказались покрашенными в один цвет. А такого на шахматной доске никогда не было, и быть не может!

Теперь у Бобби есть всего одна ночь на исправление своей ошибки. Казалось бы, времени много. Но все усложняется тем, что перекрасить поле шахматной доски достаточно сложная задача, ведь надо аккуратно снять старый слой краски. Поэтому Бобби хочет перекрасить наименьшее возможное число полей. Помогите ему написать программу, которая найдет: какие поля доски ему надо перекрасить.

Единственным требованием к шахматной доске, которая должна получиться в результате, является то, что любые два соседних поля покрашены в разные цвета. Ну, и, конечно, любое поле должно быть либо белым, либо черным.

Соседними полями на шахматной доске Хосе Раулевич считает поля, имеющие общую сторону.

Код

#include <bits/stdc++.h>

using namespace std;
int n, m;
vector< vector < char > > a;

vector<vector<char > > t1;
vector<vector<char > > t2;
void solve(int &s1, int &s2)
{
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(a[i][j] != t1[i][j])
                ++s1;
            if(a[i][j] != t2[i][j])
                ++s2;
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        vector<char> t(m);
        for(int j = 0; j < m; ++j)
           cin >> t[j];
        a.push_back(t);
    }
    for(int i = 0; i < n; ++i){
        vector<char> t(m);
        t1.push_back(t);
        t2.push_back(t);
    }
    for(int i = 0; i < n; ++i){
        if(i % 2 == 0){
            for(int j = 0; j < m; ++j){
                if(j % 2 == 0){
                    t1[i][j] = 'W';
                    t2[i][j] = 'B';
                }
                else{
                    t1[i][j] = 'B';
                    t2[i][j] = 'W';
                }
            }
        }
        else{
            for(int j = 0; j < m; ++j){
                if(j % 2 == 0){
                    t1[i][j] = 'B';
                    t2[i][j] = 'W';
                }
                else{
                    t1[i][j] = 'W';
                    t2[i][j] = 'B';
                }
            }
        }
    }
    int s1 = 0, s2 = 0;
    solve(s1, s2);
    if(s1 <= s2){
        cout << s1 << endl;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(a[i][j] != t1[i][j])
                    cout << i + 1<< ' ' << j + 1 << endl;
    }
    else{
        cout << s2 << endl;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(a[i][j] != t2[i][j])
                    cout << i + 1<< ' ' << j + 1<< endl;
    }
    return 0;
}

         

Администратор Photo Автор: Администратор


Перестарался :-))


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться