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

Problem 2: Connect the Cows [Brian Dean, 2012] - C++

Восстановить пароль Регистрация
 
nikusha
0 / 0 / 0
Регистрация: 11.02.2011
Сообщений: 4
06.03.2012, 22:08     Problem 2: Connect the Cows [Brian Dean, 2012] #1
Problem 2: Connect the Cows [Brian Dean, 2012]

Каждый день Фермер Джон обходит свою ферму, чтобы проведать N
(1 <= N <= 10) своих коров.

Местоположение каждой из его коров описывается точкой на координатной
плоскости, а ФД начинает в точке (0,0). Чтобы сделать маршрут более
интересным, ФД ходит только параллельно осям координат (на север, юг,
восток и запад). Он меняет направление своего движения, только когда он
добирается до одной из коров. Если пожелает, он может не менять
направление своего движения, проходя через местоположение коровы.
Когда ФД меняет направление движения, он может менять его на 90 или 180
градусов. ФД должен вернутся в исходную точку после посещения всех
коров.

Пожалуйста, вычислите общее количество способов, которыми ФД может
посетить всех своих коров, если он изменит направление своего движения
ровно один раз у каждой коровы. Не изменяя направление движения, он
может ходить мимо коровы произвольное количество раз. Один и тот же
геометрический путь, пройденный в прямом и обратном направлениях,
считается как два различных маршрута.

PROBLEM NAME: connect

INPUT FORMAT:

* Строка 1: Целое число N.

* Строки 2..1+N: Строка i+1 содержит x и y координаты (разделенные пробелом)
для i-ой точки(все числа в диапазоне -1000...1000).

SAMPLE INPUT (файл connect.in):

4
0 1
2 1
2 0
2 -5

INPUT DETAILS:

Всего 4 коровы, в позициях (0,1), (2,1), (2,0), (2,-5).

OUTPUT FORMAT:

* Строка 1: Количество различных маршрутов ФД
(может быть равным 0, если их нет)


SAMPLE OUTPUT (файл connect.out):

2

OUTPUT DETAILS:

Всего есть два различных маршрута
1-2-4-3 или 3-4-2-1
прежде чем ФД вернется в точку (0,0).

Language:
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2012, 22:08     Problem 2: Connect the Cows [Brian Dean, 2012]
Посмотрите здесь:

C++ В чем problem ребята?
Problem : pow C++
Intialization problem C++
C++ Возникла problem по классам
C++ connect,slots
C++ Problem - Undefined reference to
C++ Problem - switch - не работает break
C++ Problem with passing a list variable by a reference

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
magirus
06.03.2012, 22:11
  #2
 Комментарий администратора 
может вы наконец сами найдете где на форуме находится раздел С++?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.03.2012, 04:56     Problem 2: Connect the Cows [Brian Dean, 2012] #3
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
64
65
66
67
68
69
70
71
72
#include <stdio.h>
bool mas_kontr[10];
int N, mas[10][2], res;
void rec(int x, int y, int napr, int col)
{
    if(col==N)
    {
        if(x==0)
        {
            if(napr==1 && y<0)
                res++;
            if(napr==3 && y>0)
                res++;
        }
        if(y==0)
        {
            if(napr==0 && x<0)
                res++;
            if(napr==2 && x>0)
                res++;
        }
        return;
    }   
    for(int i=0; i<N; i++)
        if(!mas_kontr[i])
        {
            if(napr==0 && y==mas[i][1] && x<mas[i][0])
            {
                mas_kontr[i]=true;
                rec(mas[i][0], mas[i][1], 1, col+1);
                rec(mas[i][0], mas[i][1], 2, col+1);
                rec(mas[i][0], mas[i][1], 3, col+1);
                mas_kontr[i]=false;             
            }
            if(napr==2 && y==mas[i][1] && x>mas[i][0])
            {
                mas_kontr[i]=true;
                rec(mas[i][0], mas[i][1], 1, col+1);
                rec(mas[i][0], mas[i][1], 0, col+1);
                rec(mas[i][0], mas[i][1], 3, col+1);
                mas_kontr[i]=false;             
            }
            if(napr==1 && x==mas[i][0] && y<mas[i][1])
            {
                mas_kontr[i]=true;
                rec(mas[i][0], mas[i][1], 0, col+1);
                rec(mas[i][0], mas[i][1], 2, col+1);
                rec(mas[i][0], mas[i][1], 3, col+1);
                mas_kontr[i]=false;             
            }
            if(napr==3 && x==mas[i][0] && y>mas[i][1])
            {
                mas_kontr[i]=true;
                rec(mas[i][0], mas[i][1], 0, col+1);
                rec(mas[i][0], mas[i][1], 2, col+1);
                rec(mas[i][0], mas[i][1], 1, col+1);
                mas_kontr[i]=false;             
            }
        }
}
 
int main()
{ 
    freopen("connect.in","r",stdin);
    freopen("connect.out","w",stdout);
    scanf("%d", &N);
    for(int i=0; i<N; i++)
        scanf("%d %d", &mas[i][0], &mas[i][1]);
    rec(0,0,0,0);rec(0,0,1,0);rec(0,0,2,0);rec(0,0,3,0);
    printf("%d", res); 
    return 0;
}
Yandex
Объявления
07.03.2012, 04:56     Problem 2: Connect the Cows [Brian Dean, 2012]
Ответ Создать тему
Опции темы

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