Информатика: Расстановка шахматных фигур — различия между версиями
| Строка 1: | Строка 1: | ||
| − | |||
<div class="mw-collapsible mw-collapsed" style="width:100%" > | <div class="mw-collapsible mw-collapsed" style="width:100%" > | ||
'''[[Лебедев Станислав]]''' <div class="mw-collapsible-content"> | '''[[Лебедев Станислав]]''' <div class="mw-collapsible-content"> | ||
| Строка 344: | Строка 343: | ||
step(top,i,st + 1); | step(top,i,st + 1); | ||
} | } | ||
| − | else | + | else[[:File:Шахматы.rar]] |
{ | { | ||
set_figure(x,top); | set_figure(x,top); | ||
| Строка 411: | Строка 410: | ||
return 0; | return 0; | ||
} | } | ||
| + | |||
| + | [[Шахматы|Шахматы.rar]] | ||
Версия 16:55, 17 декабря 2015
Функционал программы: получение всевозможных расстановок n однотипных шахматных фигур первой линии на поле n на n,таких,чтобы фигуры не били друг друга(считается,что фигуры одного цвета также могут бить друг друга) или получения максимального количества фигур первой линии,которые могут стоять на доске n*n; Идея алгоритма: рекурсивно вызвается функция,которая ставит фигуру в пустую и небитую клетку, а также отмечает клетки,которые эта фигура бьет. Рекурсия продолжается до тех пор,пока либо не будет достигнуто нужное количество, либо не будет возможности поставить фигуру. После выхода из рекурсии начинается "обратный ход", в котором отмеченные как битые на этом шаге,"размечаются"(снимается отметка,что эта клетка бьется),а место,занятое самой фигурой, запоминается.
<syntaxhighlight lang="cpp" line start="1" enclose="div">
- include <iostream>
- include <math.h>
- include <cmath>
using namespace std;
int n,type, *a, *stak, variant, maxst = 0;
void king(int x, int &top) //отметить битые клетки королем {
// 012 // 345 // 678
//0
if (((x % n) > 1) && ((x / n) > 1))
{
int ii = x - n - 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
//1
if ((x / n) > 0)
{
int ii = x - n;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
//2
if (((x % n) < (n - 1)) && ((x / n) > 0))
{
int ii = x - n + 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
//3
if ((x % n) > 0)
{
int ii = x - 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
//5
if ((x % n) < (n - 1))
{
int ii = x + 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
//6
if (((x % n ) > 0) && ((x / n) < (n - 1)))
{
int ii = x + n - 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
//7
if ((x / n ) < (n - 1))
{
int ii = x + n;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
//8
if (((x % n ) < (n - 1)) && ((x / n) < (n - 1)))
{
int ii = x + n + 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
}
void bishop(int x, int &top) //отметить битые клетки слоном {
//вверх влево
for (int i = (x - (n + 1)); ((i >= 0) && ((i%n) != (n-1))); i -= (n+1))
{
if (a[i] != -2)
{
a[i]++;
stak[top] = i;
top++;
}
}
//вниз вправо
for (int i = (x + (n + 1)); ((i < n*n) && ((i%n) != 0)); i += (n+1))
{
if (a[i] != -2)
{
a[i]++;
stak[top] = i;
top++;
}
}
//вверх вправо
for (int i = x - (n - 1); ((i >= 0) && ((i%n) != 0)); i -= (n-1))
{
if (a[i] != -2)
{
a[i]++;
stak[top] = i;
top++;
}
}
//вниз влево
for (int i = x + (n - 1); ((i < n*n) && ((i%n) != (n-1))); i += (n-1))
{
if (a[i] != -2)
{
a[i]++;
stak[top] = i;
top++;
}
}
}
void knight(int x, int &top) //отметить битые клетки конем {
if (((x%n) > 0) && (x/n) > 1)
{
int ii = x - 2*n - 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
if (((x%n) > 1) && (x/n) > 0)
{
int ii = x - n - 2;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
if (((x%n) > 1) && (x/n) < (n - 1))
{
int ii = x + n - 2;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
if (((x%n) > 0) && (x/n) < (n - 2))
{
int ii = x + 2*n - 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
if (((x%n) < (n - 1)) && (x/n) < (n - 2))
{
int ii = x + 2*n + 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
if (((x%n) < (n - 2)) && (x/n) < (n - 1))
{
int ii = x + n + 2;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
if (((x%n) < (n - 2)) && (x/n) < 0)
{
int ii = x - n + 2;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
if (((x%n) < (n - 1)) && (x/n) < 1)
{
int ii = x - 2*n + 1;
if (a[ii] != -2)
{
a[ii]++;
stak[top] = ii;
top++;
}
}
}
void rook(int x, int &top) //отметить битые клетки ладьей {
int k = x - (x % n);
while ((k/n) == (x/n))
{
if ((k != x) && (a[k] != -2))
{
a[k]++;
stak[top] = k;
top++;
}
k ++;
}
k = (x % n);
while (((k/n)) != n)
{
if ((k != x) && (a[k] != -2))
{
a[k]++;
stak[top] = k;
top++;
}
k += n;
}
} void set_figure(int x, int &top) //ставим фигуры на доску {
//отмечаем "битые" клетки
switch (type)
{
//король
case 1:
{
king(x,top);
break;
}
//слон case 2: { bishop(x,top);
break;
}
//конь case 3: { knight(x,top); break; } //ладья
case 4:
{
rook(x,top);
break;
}
//ферзь
case 5:
{
rook(x,top);
bishop(x,top);
break;
}
}
//отмечаем,что в данной клетке стоит фигура
a[x] = -1;
stak[top] = x; top++;
}
void step(int top,int x,int st) { int xtop = top; switch (variant) { case 1: { if (st != (n - 1)) { set_figure(x,top); for (int i = 0; i < (n*n); i++) if (a[i] == 0) step(top,i,st + 1); } elseFile:Шахматы.rar { set_figure(x,top);
cout << endl;
for (int i = 0; i < (n*n); i++) { cout.width(3); if (((i % n) == 0) && (i != 0)) cout << endl; if (a[i] == -1) cout << 1; else cout << 0; } cout << endl; } break; } case 2: { set_figure(x,top); if ((st+1) > maxst) maxst = st + 1; for (int i = 0; i < (n*n); i++) if (a[i] == 0) step(top,i,st+1); break; } }
// обратный ход
for (int i = xtop; i < top; i++)
{
if ((a[stak[i]] != -1) && (a[stak[i]] != -2))
a[stak[i]]--;
else
//не забываем отметить,что фигура уже здесь стояла(чтобы избежать повторов)
if (a[stak[i]] == -1)
a[stak[i]] = -2;
// cerr << " Back " << stak[i] << endl;
}
}
int main() {
//cin >> n >> type >> variant; n = 5; type = 4;
variant = 1;
a = new int[n*n]; stak = new int[n*n*4];
for (int i = 0; i < (n*n); i++)
{
for (int j = 0; j < (n*n); j++)
a[j] = 0;
if (variant == 1)
cout << "__________________________________" << endl;
step(0,i,0);
}
if (variant == 2) cout << maxst;
return 0;
}
Шахматы.rar
