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

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

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

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

27.03.2012, 22:34. Просмотров 1173. Ответов 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++
C++ Минимальное количество прямых через заданное множество точек
C++ Найти минимальное количество пересадок между двумя городами
Минимальное количество байт, которое займёт отрицательное число C++
Вывести числа от 1 до 30 следующим образом (и за минимальное количество строк): C++
Вывести минимальное количество C++
C++ Определить количество, минимальное и максимальное из введенных чисел
C++ Посчитать количество столбцов в строке, разделённых произвольным количеством белых знаков
Найти минимальное количество купюр для оплаты суммы C++
C++ В каждом столбце обнулить минимальное количество элементов
Реализовать программу по распределению 8 слонов по шахматной доске C++
Минимальное число белых слонов C++

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

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

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

Загляни ещё в эту тему.
понять рекурсию
valeriikozlov
Эксперт C++
4663 / 2489 / 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;
}
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 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