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

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

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

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

27.03.2012, 22:34. Просмотров 1222. Ответов 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.03.2012, 22:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Минимальное количество белых слонов (C++):

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

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

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

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

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

Определить количество, минимальное и максимальное из введенных чисел - C++
Пользователь вводит последовательность чисел. Окончание ввода – ввод числа ноль. Программа должна определить количество, минимальное и...

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

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

Загляни ещё в эту тему.
понять рекурсию
0
valeriikozlov
Эксперт С++
4670 / 2496 / 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;
}
1
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 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 при моём рекурсивном решении это точно переполнит стек!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.03.2012, 13:59
Привет! Вот еще темы с ответами:

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

Найти минимальное количество купюр для оплаты суммы - C++
Я саму программу написал, да вот во время выполнения, в консоли, после ввода мною переменной summa, вообще ничего не происходит. Консоль...

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

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


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

Или воспользуйтесь поиском по форуму:
6
Yandex
Объявления
28.03.2012, 13:59
Ответ Создать тему
Опции темы

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