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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
kairat_s1306
Сообщений: n/a
16.10.2010, 11:08     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #1
Описание

Ферзь - самая сильная шахматная фигура, которая за один ход может перемещатся на льбое число полей по вертикали, горизонтали или диогонали (при условии, что на его пути нет фигур). Клетка бъется ферзем, если он может попасть на нее одним ходом. На доске 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
16.10.2010, 13:45     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #2
Сдается мне что это олимпиадная задача
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
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
2769 / 1582 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 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
2769 / 1582 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
17.10.2010, 13:07     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #7
Цитата Сообщение от archinko Посмотреть сообщение
s остается нулем. Тестил примером.
Напиши этот пример, посмотрю.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,390
17.10.2010, 15:09     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #8
Цитата Сообщение от archinko Посмотреть сообщение
Кстати в примере неправильный ответ. Если я правильно понял входные данные, то на доске размером 3х3 с двумя ферзями [3][3] и [2][3] все клетки будут биты, то есть ответ 0.
Ага, неправильный
Somebody
2769 / 1582 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
17.10.2010, 15:44     Посчитать количество пустых клеток шахматной доски, которые не бьются ни одним ферзем #9
А, понял. Просто проверял на 8x8, там этого глюка нет. 14-я строчка должна быть:
C++
1
int nb = n + 7 >> 3;
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
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++

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

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

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