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

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

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

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

16.10.2010, 11:08. Просмотров 1266. Ответов 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++ Закрасить участок шахматной доски
Разрезание шахматной доски C++
Король шахматной доски C++
Посчитать количество занятых клеток кроссворда C++
Обход шахматной доски конем C++
C++ Задачка. Поле шахматной доски
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
 Аватар для odip
7151 / 3291 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
16.10.2010, 13:45     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #2
Сдается мне что это олимпиадная задача
Nameless One
Эксперт С++
 Аватар для Nameless One
5760 / 3409 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
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
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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
13 / 13 / 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
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 1
17.10.2010, 13:07     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #7
Цитата Сообщение от archinko Посмотреть сообщение
s остается нулем. Тестил примером.
Напиши этот пример, посмотрю.
Nameless One
Эксперт С++
 Аватар для Nameless One
5760 / 3409 / 255
Регистрация: 08.02.2010
Сообщений: 7,412
17.10.2010, 15:09     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #8
Цитата Сообщение от archinko Посмотреть сообщение
Кстати в примере неправильный ответ. Если я правильно понял входные данные, то на доске размером 3х3 с двумя ферзями [3][3] и [2][3] все клетки будут биты, то есть ответ 0.
Ага, неправильный
Somebody
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 1
17.10.2010, 15:44     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #9
А, понял. Просто проверял на 8x8, там этого глюка нет. 14-я строчка должна быть:
C++
1
int nb = n + 7 >> 3;
odip
Эксперт С++
 Аватар для odip
7151 / 3291 / 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++ Написать шаблон шахматной доски
C++ Посчитать в строке количество слов с одним пробелом и с произвольным их количеством
Количество обходов шахматной доски конём (с возвратом в начальную клетку) C++

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

Или воспользуйтесь поиском по форуму:
Somebody
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем
Ответ Создать тему
Опции темы

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