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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
kairat_s1306
#1

Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем - C++

16.10.2010, 11:08. Просмотров 1317. Ответов 10
Метки нет (Все метки)

Описание

Ферзь - самая сильная шахматная фигура, которая за один ход может перемещатся на льбое число полей по вертикали, горизонтали или диогонали (при условии, что на его пути нет фигур). Клетка бъется ферзем, если он может попасть на нее одним ходом. На доске N x N расставлено К ферзей. Посчитайте количество пустых клеток доски, которые не бьются ни одним ферзем.
Формат входных данных

Первая строка входного файла содержит два целых числа N и K (1 <= N <= 10000, 1 <= K <= 100000). Каждая из следующих K строк содержит по два числа - номера строк и столбцов, на которых стоит соответствующий ферзь (строки и столбцы нумеруются целыми числами от 1 до N). Позиции всех ферзей различны. Числа в строках разделены пробелом.
Формат выходных данных

Выведите одно целое число - ответ к задаче.

Примеры:
ввод

3 2
3 3
2 3

вывод
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.10.2010, 11:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем (C++):

Количество обходов шахматной доски конём (с возвратом в начальную клетку) - C++
Всем добрый день, нужна помощь. Нужно найти на доске n*m количество обходов доски. n,m &lt;=6. С последней клетки нужно обязательно вернуться...

Посчитать количество занятых клеток кроссворда - C++
Помогите,пожалуйста решить задачу. Кроссворд размещен в квадрате. Строки и столбцы квадрата нумеруются снизу вверх и слева направо,...

Посчитать количество пустых промежутков - пробелов и табуляций - C++
Дана одна строка, длина которой может быть от 1 до 100 символов. Найдите количество &quot;пустых промежутков&quot; в этой строке, то есть фрагментов...

Определить сколько клеток по периметру доски - C++
Задача с условным оператором. В каждую крайнюю клетку квадратной доски поставили по фишке. Могло ли оказаться, что выставлено ровно k...

Король шахматной доски - C++
Король шахматной доски размером 8х8 находится на коне в одной из клеток своего королевства. Он очень озабочен тем, что некоторые клетки его...

Разрезание шахматной доски - C++
Написать программу нахождения всех способов разрезания шахматной доски с числом клеток nxn (n-четное) на две одинаковые по форме части (не...

10
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
16.10.2010, 13:45 #2
Сдается мне что это олимпиадная задача
0
Nameless One
Эксперт С++
5775 / 3425 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
16.10.2010, 21:30 #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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <stdlib.h>
 
int isUnique(size_t** arr, size_t max) {
  for(size_t i = 0; i < max; ++i)
    if((arr[i][0] == arr[max][0]) &&
       (arr[i][1] == arr[max][1]))
      return 0;
 
  return 1;
}
 
int isFree(size_t** arr, size_t max, size_t row, size_t col) {
  for(size_t i = 0; i < max; ++i) {
    if((arr[i][0] == row) || (arr[i][1] == col))
      return 0;
    else if((abs(((int) row) - ((int) arr[i][0]))) ==
        (abs(((int) col) - ((int) arr[i][1]))))
      return 0;
  }
  return 1;
}
 
int main(void) {
  
  size_t N, K;
  size_t** queens;
  size_t result = 0;
  FILE* f;
 
  if((f = fopen("input.txt", "r")) == NULL) {
    perror("Can't open file for input");
    return 1;
  }
 
  fscanf(f, "%u %u", &N, &K);
 
  if(ferror(f)) {
    perror("Can't read from file");
    return 1;
  }
 
  queens = (size_t **) calloc(K, sizeof(size_t *));
 
  if(!queens) {
    perror("Can't allocate memory");
    return 1;
  }
 
  for(size_t i = 0; i < K; ++i) {
     
    queens[i] = (size_t *) calloc(2, sizeof(size_t));
    
    if(!queens[i]) {
      perror("Can't allocate memory");
      return 1;
    }
  }
 
  for(size_t i = 0; i < K; ++i) {
    fscanf(f, "%u %u", queens[i], queens[i] + 1);
 
    if(!isUnique(queens, i)) {
      perror("Queens must be unique");
      return 1;
    }
 
    if(ferror(f)) {
      perror("Can't read from file");
      return 1;
    }
  }
 
  for(size_t i = 1; i <= N; ++i) {
    for(size_t j = 1; j <= N; ++j) {
      if(isFree(queens, K, i, j)) {
    ++result;
      }
    }
  }
 
  printf("Result = %u\n", result);
 
  for(size_t i = 0; i < K; ++i)
    free(queens[i]);
 
  free(queens);
 
  fclose(f);
 
  return 0;
}
Цитата Сообщение от odip Посмотреть сообщение
Сдается мне что это олимпиадная задача
Максимум - школьного уровня
0
AemClock
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
16.10.2010, 22:18 #4
Максимум - школьного уровня
А Вы попробуйте запустить программу с N = 10000 и K = 100000. Я думаю не стоит ждать завершения работы, так как это произойдет не скоро.

Здесь не все так просто, думать надо.
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
16.10.2010, 23:30 #5
Если аккуратно закодить, считает за 12 секунд на моём компе (при максимальных n и k) и потребляет 12 МБ памяти (1 бит на клетку).
sync_with_stdio(false) - это на всякий случай, с вводом вроде проблем никогда не было, а вот с таким, что при редиректе вывода в файл скомпилированое Borland'ом тормозит, встречался.
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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxN = 10000;
char a[maxN][(maxN + 7) / 8];
 
int main()
{
    int n, k;
    cin.sync_with_stdio(false);
    cin >> n >> k;
    int nb = n >> 3;
    for (int i = 0; i < k; i++)
    {
        int x, y;
        cin >> x >> y;
        x--, y--;
        int xb = x >> 3;
        char xm = 1 << (x & 7);
        for (int cxb = 0; cxb < nb; cxb++)
            a[y][cxb] = -1;
        for (int cy = 0; cy < n; cy++)
            a[cy][xb] |= xm;
        for (int i = -min(x, y), e = n - max(x, y); i < e; i++)
            a[y + i][(x + i) >> 3] |= 1 << ((x + i) & 7);
        for (int i = -min(x, n - 1 - y), e = n - max(x, n - 1 - y); i < e; i++)
            a[y - i][(x + i) >> 3] |= 1 << ((x + i) & 7);
    }
    char m = ~(-1 << (n & 7));
    for (int y = 0; y < n; y++)
        a[y][n >> 3] &= m;
    int s = 0;
    for (int y = 0; y < n; y++)
        for (int xb = 0; xb < nb; xb++)
        {
            int t = a[y][xb];
            s += (t >> 0 & 1) + (t >> 1 & 1) + (t >> 2 & 1) + (t >> 3 & 1) +
                (t >> 4 & 1) + (t >> 5 & 1) + (t >> 6 & 1) + (t >> 7 & 1);
        }
    cout << n * n - s;
}
0
archinko
14 / 14 / 2
Регистрация: 02.03.2010
Сообщений: 29
17.10.2010, 02:20 #6
Добавлю и я свой кривой вариант

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
class Table{
    int N;
    int **T;
    public:
        Table();
        Table(int raz);
        void AddFerz(int x,int y);
        void showTable();
        int ZeroCount();
};
 
Table::Table(int raz)
{
    N=raz; 
    T=(int**)calloc(N,sizeof(int*));
    for(int n=0;n<N;n++)
        T[n]=(int*)calloc(N,sizeof(int));
    for(int n=0;n<N;n++)
    {   
        for(int k=0;k<N;k++)
        {
            T[n][k]=0;
        }
    }   
}
 
void Table::AddFerz(int x,int y)
{
    T[x][y]=1;
    for(int n=1;n<N;n++)
    {
        if(x+n<N&&y<N&&y>=0&&x+n>=0)T[x+n][y]=1;
        if(x-n<N&&y<N&&y>=0&&x-n>=0)T[x-n][y]=1;
        if(x<N&&y+n<N&&y+n>=0&&x>=0)T[x][y+n]=1;
        if(x<N&&y-n<N&&y-n>=0&&x>=0)T[x][y-n]=1;
 
        if(x+n<N&&y+n<N&&y+n>=0&&x+n>=0)T[x+n][y+n]=1;
        if(x-n<N&&y-n<N&&y-n>=0&&x-n>=0)T[x-n][y-n]=1;
        if(x+n<N&&y-n<N&&y-n>=0&&x+n>=0)T[x+n][y-n]=1;
        if(x-n<N&&y+n<N&&y+n>=0&&x-n>=0)T[x-n][y+n]=1;
        
    }
}
 
void Table::showTable()
{
    for(int n=0;n<N;n++)
    {   
        for(int k=0;k<N;k++)
        {
        cout<<T[n][k]<<" ";
        }
        cout<<endl;
    }
}
 
int Table::ZeroCount()
{
    int res=0;
    for(int n=0;n<N;n++)
    {
        for(int k=0;k<N;k++)
        {
            if(!T[n][k]) res++;
        }
    }
    return res;
}
 
    
int main()
{
    int N,K,**ferzi;
    cin>>N>>K;
    ferzi=(int**)calloc(2,sizeof(int*));
    ferzi[0]=(int*)calloc(K,sizeof(int));
    ferzi[1]=(int*)calloc(K,sizeof(int));
    for(int n=0;n<K;n++)
    {
        cin>>ferzi[0][n]>>ferzi[1][n];
        --ferzi[0][n];
        --ferzi[1][n];
    }
 
    Table t(N);
    for(int n=0;n<K;n++)
        t.AddFerz(ferzi[0][n],ferzi[1][n]);
    
    t.showTable();
    cout <<endl<< t.ZeroCount();
    return 777;
}
Кстати в примере неправильный ответ. Если я правильно понял входные данные, то на доске размером 3х3 с двумя ферзями [3][3] и [2][3] все клетки будут биты, то есть ответ 0.

Добавлено через 30 минут
В коде Somebody неправильно выводит ответ. Походу сдесь
C++
1
cout << n * n - s
s остается нулем. Тестил примером.
1
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
17.10.2010, 13:07 #7
Цитата Сообщение от archinko Посмотреть сообщение
s остается нулем. Тестил примером.
Напиши этот пример, посмотрю.
0
Nameless One
Эксперт С++
5775 / 3425 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
17.10.2010, 15:09 #8
Цитата Сообщение от archinko Посмотреть сообщение
Кстати в примере неправильный ответ. Если я правильно понял входные данные, то на доске размером 3х3 с двумя ферзями [3][3] и [2][3] все клетки будут биты, то есть ответ 0.
Ага, неправильный
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
17.10.2010, 15:44 #9
А, понял. Просто проверял на 8x8, там этого глюка нет. 14-я строчка должна быть:
C++
1
int nb = n + 7 >> 3;
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
17.10.2010, 16:22 #10
Если аккуратно закодить, считает за 12 секунд на моём компе
На олимпиадных задачах время счета ограничено - 1-2 секунды
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
18.10.2010, 16:52 #11
Ой, это на 10000 было 12 секунд, а не на 100000. Если что, там ещё в 7-й строке ошибка, надо
char a[maxN][maxN / 8 + 1], иначе в 33-й за пределы выходит. Короче, неважно, до меня дошло (что-то оно долго доходило):
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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxN = 10000;
bool ar[maxN], af[maxN], ad0[maxN * 2], ad1[maxN * 2];
 
int main()
{
    int n, k;
    cin.sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        int x, y;
        cin >> x >> y;
        x--, y--;
        ar[y] = true;
        af[x] = true;
        ad0[x + y] = true;
        ad1[x + n - 1 - y] = true;
    }
    int s = 0;
    for (int y = 0; y < n; y++)
        for (int x = 0; x < n; x++)
            s += ar[y] || af[x] || ad0[x + y] || ad1[x + n - 1 - y];
    cout << n * n - s;
}
0
18.10.2010, 16:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.10.2010, 16:52
Привет! Вот еще темы с ответами:

Задачка. Поле шахматной доски - C++
Поле шахматной доски задается парой натуральных чисел: Первое указывает номер вертикали при счете слева направо, второе - номер горизонтали...

Закрасить участок шахматной доски - C++
Люди помогите плиз, у меня в С++ вообще башка не варит((( написать программу для выполнения следующей задачи (): Нужно решить такую...

Написать шаблон шахматной доски - C++
Всем доброго времени суток! Я только начала учить циклы. Пока тяжело писать коды. Помогите, пожалуйста, написать программу, которая выводит...

Обход конём шахматной доски - C++
Приветствую всех форумчан! Нужно решить задачу: обойти конём шахматное поле размером n*n (n&lt;=8), побывав на каждой клетке не более одного...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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