Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
erioik
1 / 1 / 0
Регистрация: 22.10.2010
Сообщений: 26
#1

Минимальное количество белых слонов - C++

27.03.2012, 22:34. Просмотров 1204. Ответов 5
Метки нет (Все метки)

Условие
Имеется шахматная доска N<=1 000 на M <=1 000 клеток (верхний левый квадрат доски имеет координаты (1,1)). Некоторые поля не ней заняты белыми фигурами, но не слонами (конь, ладья, король, королева) и белыми пешками. Каждая занятое поле определяется числом - (минус) 1, а свободное – 0. Необходимо определить минимальное количество белых слонов, которые необходимо расставить на доске, чтобы при постановке черной фигуры в любое оставшееся свободное поле она могла быть сбита одним из этих слонов за некоторое количество ходов.

Входные данные: in.txt
· В первой строке задаются размеры поля: N и M.
· Следующие N строк файла задают данные поля (по M чисел в строке).
Числа в строках разделены одним или несколькими пробелами.

Выходные данные: out.txt
Единственная строка выходного файла содержит минимальное число белых слонов.

Пример
in.txt
5 3
0 0 0
0 0 0
-1 0 -1
-1 -1 0
-1 0 0


out.txt
3
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.03.2012, 22:34     Минимальное количество белых слонов
Посмотрите здесь:

Минимальное число белых слонов - C++
Имеется шахматная доска N × M клеток. Некоторые поля на ней заняты белыми фигурами, но не слонами (конь, ладья, король, ферзь) и белыми...

Посчитать количество столбцов в строке, разделённых произвольным количеством белых знаков - C++
Необходимо посчитать количество столбцов в строке, разделённых произвольным количеством белых знаков (кроме знака конца стоки). Также...

Вывести минимальное количество - C++
Даны монеты номиналом 1, 2, 5, 10, 25, 50. Нужно написать программу, в которую вводится любое значение(сумма монет, т.е может быть: 60,...

Реализовать программу по распределению 8 слонов по шахматной доске - C++
Добрый день. Нужно реализовать программу по распределению 8 слонов по шахматной доске, которые не должны друг друга пересекать. Что сделать...

Удалить символы из строки за минимальное количество ходов. - C++
Удалить символы из строки за минимальное количество ходов. Пример input.txt acdcbbc output.txt 4 вот что Я...

В каждом столбце обнулить минимальное количество элементов - C++
Пусть задан двумерный массив n*m, состоящий из натуральных чисел. В каждом столбце обнулить минимальное количество так, чтобы, сумма...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
27.03.2012, 22:51     Минимальное количество белых слонов #2
Цитата Сообщение от erioik Посмотреть сообщение
она могла быть сбита одним из этих слонов за некоторое количество ходов.
Так слоны могут бить за несколько ходов? Ну тогда я ставлю одного слона на чёрную клетку, одного на белую и бью любое поле за два хода! Или суть в том, что им встречные фигуры мешают? Или всё же должны бить за один ход?
erioik
1 / 1 / 0
Регистрация: 22.10.2010
Сообщений: 26
27.03.2012, 23:01  [ТС]     Минимальное количество белых слонов #3
скорее всего встречные мешают.
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
27.03.2012, 23:14     Минимальное количество белых слонов #4
Скорее всего алгоритм аналогичен поиску выхода из лабиринта. Я вчера только обсуждал его в одной теме. Ты ставишь слона на одну из белых клеток, и начинаешь рекурсивно "раскрашивать" все клетки, в которые можешь пойти из исходной. затем ставишь второго слона на нераскрашенную белую клетку и продолжаешь. Так пока не раскрасишь все белые клетки.

Далее ставишь слона на некрашенную чёрную клетку и начинаешь красить чёрные клетки. В конце, когда все клетки закрашены, выводишь ответ, сколько тебе понадобилось слонов!

Загляни ещё в эту тему.
понять рекурсию
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.03.2012, 00:30     Минимальное количество белых слонов #5
рекурсией можно решить эту задачу, но рекурсия является не единственным вариантом решения.
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
#include<stdio.h>
#include<malloc.h>
int main()
{
      freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
    int **a, i, j, i_st, i_end, N, M, col=0;
    struct tt{
        int x, y;
    };
    tt *Q=(tt*)malloc(500000*sizeof(tt));   
    scanf("%d %d", &N, &M);
    a=(int**)malloc(N*sizeof(int*));
    for(i=0; i<N; i++)
    {
        a[i]=(int*)malloc(M*sizeof(int));
        for(j=0; j<M; j++)
            scanf("%d", &a[i][j]);
    }
    for(i=0; i<N; i++)
        for(j=0; j<M; j++)
            if(a[i][j]==0)
            {
                i_st=0; i_end=1; Q[0].x=i; Q[0].y=j;
                a[i][j]=1; col++;
                while(i_st<i_end)
                {
                    if(Q[i_st].x>0)
                    {
                        if(Q[i_st].y>0 && a[Q[i_st].x-1][Q[i_st].y-1]==0)
                        {
                            Q[i_end].x=Q[i_st].x-1; Q[i_end++].y=Q[i_st].y-1; a[Q[i_st].x-1][Q[i_st].y-1]=1;
                        }
                        if(Q[i_st].y<M-1 && a[Q[i_st].x-1][Q[i_st].y+1]==0)
                        {
                            Q[i_end].x=Q[i_st].x-1; Q[i_end++].y=Q[i_st].y+1; a[Q[i_st].x-1][Q[i_st].y+1]=1;
                        }                       
                    }
                    if(Q[i_st].x<N-1)
                    {
                        if(Q[i_st].y>0 && a[Q[i_st].x+1][Q[i_st].y-1]==0)
                        {
                            Q[i_end].x=Q[i_st].x+1; Q[i_end++].y=Q[i_st].y-1; a[Q[i_st].x+1][Q[i_st].y-1]=1;
                        }
                        if(Q[i_st].y<M-1 && a[Q[i_st].x+1][Q[i_st].y+1]==0)
                        {
                            Q[i_end].x=Q[i_st].x+1; Q[i_end++].y=Q[i_st].y+1; a[Q[i_st].x+1][Q[i_st].y+1]=1;
                        }                       
                    }                   
                    i_st++;
                }
            }
    printf("%d", col);
 
return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.03.2012, 13:59     Минимальное количество белых слонов
Еще ссылки по теме:

Вывести числа от 1 до 30 следующим образом (и за минимальное количество строк): - C++
Вывести числа от 1 до 30 следующим образом: 1 2 3 4 5 6 … 28 29 30 помогите пожалуйста!или объясните как сделать чтобы они по...

Найти минимальное количество пересадок между двумя городами - C++
Здраствуйте!Помогите пожалуйста Кратчайший путь. Даны N городов и связи между ними в виде матрицы смежности. Требуется найти...

Минимальное количество байт, которое займёт отрицательное число - C++
Нужно узнать минимальное количество байт, которое займёт число. То есть в int у нас может быть число и 256 (00000001 00000000), которое...

Минимальное количество прямых через заданное множество точек - C++
Не могу найти ошибку в коде, помогите пожалуйста. #include &lt;cstdlib&gt; #include &lt;stdio.h&gt; #include &lt;iostream.h&gt; #include &lt;vcl.h&gt; ...


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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
28.03.2012, 13:59     Минимальное количество белых слонов #6
Моё решение. Проверял на двух файлах - работает.
файл in.txt
C++
1
2
3
4
5
6
7
8
9
8 6
 0  0  0  0  0  0
 0 -1  0 -1  0 -1
-1  0  0 -1  0  0
 0  0  0 -1 -1  0
 0 -1 -1 -1 -1  0
 0 -1  0  0  0 -1
 0  0 -1 -1  0  0
 0  0  0  0  0  0
файл in2.txt (тестовый заполненный нулями)
C++
1
2
3
4
5
6
7
8
9
8 6
 0  0  0  0  0  0
 0  0  0  0  0  0
 0  0  0  0  0  0
 0  0  0  0  0  0
 0  0  0  0  0  0
 0  0  0  0  0  0
 0  0  0  0  0  0
 0  0  0  0  0  0
Программа сама
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
#include <iostream> 
#include <fstream>
using namespace std;
const int MAXSIZE = 1000;
int width, height;
int board[MAXSIZE][MAXSIZE];
void load_board(){
    int i, j;
    ifstream txt;
    txt.open("in.txt");
    if (!txt) cout<<"Error opening in.txt"<<endl;
    txt>>height>>width;
    if ((height<2)||(height>MAXSIZE)||(width<2)||(width>MAXSIZE)){
        cerr<<"Error: invalid board size"<<endl;
    }
    for (i=0; i<height; i++)
        for (j=0; j<width; j++)
            txt>>board[j][i];
    txt.close();
}
void show_board(){
    int i, j;
    for (i=0; i<height; i++){
        for (j=0; j<width; j++)
            if (board[j][i]==-1)
                cout<<"# ";
            else
                cout<<board[j][i]<<" ";
        cout<<endl;
    }
}
void paint(int x, int y, int c){
    board[x][y]=c;
    if (y<height-1){
        if (x<width-1) if (board[x+1][y+1]==0) paint(x+1, y+1, c);
        if (x>0)       if (board[x-1][y+1]==0) paint(x-1, y+1, c);
    }
    if (y>0){
        if (x>0)       if (board[x-1][y-1]==0) paint(x-1, y-1, c);
        if (x<width-1) if (board[x+1][y-1]==0) paint(x+1, y-1, c);
    }
}
int solve(){
    int color=0;
    int i, j;
    for (j=0; j<width; j++)
        for (i=0; i<height; i++)
            if (board[j][i]==0)
                paint(j, i, ++color);
 
    return color;
}
int main(){
    char c;
    load_board();
    cout<<"given board: "<<endl;
    show_board();
    cout<<"elephants needed: "<<solve()<<endl;
    cout<<"solved board "<<endl;
    show_board();
    cin>>c;
    return 0;
}
результат работы
http://********************/show-imag...47f413d9e56203

Добавлено через 3 минуты
Цитата Сообщение от valeriikozlov Посмотреть сообщение
рекурсией можно решить эту задачу, но рекурсия является не единственным вариантом решения.

Да, ты прав на счёт рекурсии. По условию говорится, что поле может быть 1000 на 1000 при моём рекурсивном решении это точно переполнит стек!
Yandex
Объявления
28.03.2012, 13:59     Минимальное количество белых слонов
Ответ Создать тему
Опции темы

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