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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
erioik
1 / 1 / 0
Регистрация: 22.10.2010
Сообщений: 26
27.03.2012, 22:34     Минимальное количество белых слонов #1
Условие
Имеется шахматная доска 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.03.2012, 22:51     Минимальное количество белых слонов #2
Цитата Сообщение от erioik Посмотреть сообщение
она могла быть сбита одним из этих слонов за некоторое количество ходов.
Так слоны могут бить за несколько ходов? Ну тогда я ставлю одного слона на чёрную клетку, одного на белую и бью любое поле за два хода! Или суть в том, что им встречные фигуры мешают? Или всё же должны бить за один ход?
erioik
1 / 1 / 0
Регистрация: 22.10.2010
Сообщений: 26
27.03.2012, 23:01  [ТС]     Минимальное количество белых слонов #3
скорее всего встречные мешают.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.03.2012, 23:14     Минимальное количество белых слонов #4
Скорее всего алгоритм аналогичен поиску выхода из лабиринта. Я вчера только обсуждал его в одной теме. Ты ставишь слона на одну из белых клеток, и начинаешь рекурсивно "раскрашивать" все клетки, в которые можешь пойти из исходной. затем ставишь второго слона на нераскрашенную белую клетку и продолжаешь. Так пока не раскрасишь все белые клетки.

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

Загляни ещё в эту тему.
понять рекурсию
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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://hostingkartinok.com/show-imag...47f413d9e56203

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

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

Текущее время: 11:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru