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

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

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

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

16.10.2010, 11:08. Просмотров 1294. Ответов 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++
Всем добрый день, нужна помощь. Нужно найти на доске n*m количество обходов доски. n,m &lt;=6. С последней клетки нужно обязательно вернуться...

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

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

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

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

Вывод на экран шахматной доски - C++
Помогите пожалуйста написать код программы выводящей на экран шахматную доску. P.S. Я только учусь.

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
16.10.2010, 13:45     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #2
Сдается мне что это олимпиадная задача
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
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 Посмотреть сообщение
Сдается мне что это олимпиадная задача
Максимум - школьного уровня
AemClock
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
16.10.2010, 22:18     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #4
Максимум - школьного уровня
А Вы попробуйте запустить программу с N = 10000 и K = 100000. Я думаю не стоит ждать завершения работы, так как это произойдет не скоро.

Здесь не все так просто, думать надо.
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,190
Завершенные тесты: 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;
}
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 остается нулем. Тестил примером.
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,190
Завершенные тесты: 1
17.10.2010, 13:07     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #7
Цитата Сообщение от archinko Посмотреть сообщение
s остается нулем. Тестил примером.
Напиши этот пример, посмотрю.
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
17.10.2010, 15:09     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #8
Цитата Сообщение от archinko Посмотреть сообщение
Кстати в примере неправильный ответ. Если я правильно понял входные данные, то на доске размером 3х3 с двумя ферзями [3][3] и [2][3] все клетки будут биты, то есть ответ 0.
Ага, неправильный
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,190
Завершенные тесты: 1
17.10.2010, 15:44     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #9
А, понял. Просто проверял на 8x8, там этого глюка нет. 14-я строчка должна быть:
C++
1
int nb = n + 7 >> 3;
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
17.10.2010, 16:22     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #10
Если аккуратно закодить, считает за 12 секунд на моём компе
На олимпиадных задачах время счета ограничено - 1-2 секунды
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.10.2010, 16:52     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем
Еще ссылки по теме:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,190
Завершенные тесты: 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;
}
Yandex
Объявления
18.10.2010, 16:52     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем
Ответ Создать тему
Опции темы

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