Информатика: Расстановка шахматных фигур — различия между версиями

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
<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">
 +
 +
Функционал программы: получение всевозможных расстановок n однотипных шахматных фигур первой линии на поле n на n,таких,чтобы фигуры не били друг друга(считается,что фигуры одного цвета также могут бить друг друга) или получения максимального количества фигур первой линии,которые могут стоять на доске n*n;
 +
Идея алгоритма: рекурсивно вызвается функция,которая ставит фигуру в пустую и небитую клетку, а также отмечает клетки,которые эта фигура бьет. Рекурсия продолжается до тех пор,пока либо не будет достигнуто нужное количество, либо не будет возможности поставить фигуру. После выхода из рекурсии начинается "обратный ход", в котором отмеченные как битые на этом шаге,"размечаются"(снимается отметка,что эта клетка бьется),а место,занятое самой фигурой, запоминается.
  
 
<syntaxhighlight lang="cpp" line start="1" enclose="div">
 
<syntaxhighlight lang="cpp" line start="1" enclose="div">

Версия 16:24, 17 декабря 2015

Лебедев Станислав:

Функционал программы: получение всевозможных расстановок n однотипных шахматных фигур первой линии на поле n на n,таких,чтобы фигуры не били друг друга(считается,что фигуры одного цвета также могут бить друг друга) или получения максимального количества фигур первой линии,которые могут стоять на доске n*n; Идея алгоритма: рекурсивно вызвается функция,которая ставит фигуру в пустую и небитую клетку, а также отмечает клетки,которые эта фигура бьет. Рекурсия продолжается до тех пор,пока либо не будет достигнуто нужное количество, либо не будет возможности поставить фигуру. После выхода из рекурсии начинается "обратный ход", в котором отмеченные как битые на этом шаге,"размечаются"(снимается отметка,что эта клетка бьется),а место,занятое самой фигурой, запоминается.

<syntaxhighlight lang="cpp" line start="1" enclose="div">

  1. include <iostream>
  2. include <math.h>
  3. 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); } else { 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;
}