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

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск
Строка 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">
  
 
<syntaxhighlight lang="cpp" line start="1" enclose="div">
 
<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);
 +
}
 +
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;
 +
}

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

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

<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;
}
Источник — «http://tm.spbstu.ru/?title=Информатика:_Расстановка_шахматных_фигур&oldid=38305»