Рабочий стол > DL Руководство пользователя > ... > Быстрое погружение в язык C++ > Очередь knight > Просмотр
Очередь knight Войти | Зарегистрироваться   Просмотр версии для печати текущей страницы.

Добавлено Egor, последний раз изменено Egor Feb 12, 2017  (просмотр изменений)
Метки: 
(нет)


Knight1.cpp
#include <bits/stdc++.h>
using namespace std;

struct moves
{
    int x;
    int y;
    int StepNumber;
};
queue <moves> MQue;

bool Marked[8][8], Found;
int  Ex,Ey,Sx,Sy;

void StartProcess()
  {
    string s;
    getline(cin,s);
    Sx=int(s[0])-int('A');
    Sy=int(s[1])-int('1');
    Ex=int(s[3])-int('A');
    Ey=int(s[4])-int('1');
    for (int i=0; i<8; i++)
      for (int j=0; j<8; j++) Marked[i][j]=false;
    moves StartMove; StartMove.x=Sx; StartMove.y=Sy; StartMove.StepNumber=0;
    MQue.push(StartMove);
  }

void PutAll(moves CurrMove, bool &Found)
  {
   moves Cur; Cur.StepNumber=CurrMove.StepNumber;
   int steps[8][2] = {{1,-2},{1,2},{-1,-2},{-1,2},{2,-1},{2,1},{-2,-1},{-2,1}};
   Found = false;
   for (int i=0; (i<8) and (not Found); i++)
     {
       Cur.x=CurrMove.x+steps[i][0];
       Cur.y=CurrMove.y+steps[i][1];
       Found = (Ex==Cur.x) && (Ey==Cur.y);
       if ((Cur.x>=0) && (Cur.x<8) &&
           (Cur.y>=0) && (Cur.y<8) &&
           (not Marked[Cur.x][Cur.y]))
          {MQue.push(Cur); Marked[Cur.x][Cur.y]=true;};
     }
  }

int main()
{
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
 StartProcess();
 Found=(Sx==Ex) && (Sy==Ey);
 while (not Found)
   {
      moves CurrMove=MQue.front(); MQue.pop();
      CurrMove.StepNumber++;
      PutAll(CurrMove,Found);
   }
 cout << MQue.back().StepNumber; }

Knight2.cpp
#include <bits/stdc++.h>
using namespace std;
queue<int> X,Y,SN;          // Вводим три очереди по одному числу,
                            // а не одну, хранящую структуру

bool Marked[8][8], Found;
int  Ex,Ey,Sx,Sy;

void StartProcess()
  {
    string s;
    getline(cin,s);
    Sx=int(s[0])-int('A');  // нумерация с нуля
    Sy=int(s[1])-int('1');
    Ex=int(s[3])-int('A');
    Ey=int(s[4])-int('1');
    for (int i=0; i<8; i++)
      for (int j=0; j<8; j++) Marked[i][j]=false;
    X.push(Sx); Y.push(Sy); SN.push(0);
  }

void PutAll(int x, int y, int sn, bool &Found)
  {
   int steps[8][2] = {{1,-2},{1,2},{-1,-2},{-1,2},{2,-1},{2,1},{-2,-1},{-2,1}};
   Found = false;
   for (int i=0; (i<8) and (not Found); i++)
     {
       int Cx=x+steps[i][0];
       int Cy=y+steps[i][1];
       Found = (Ex==Cx) && (Ey==Cy);
       if ((Cx>=0) && (Cx<8) &&
           (Cy>=0) && (Cy<8) &&
           (not Marked[Cx][Cy]))
          {X.push(Cx); Y.push(Cy); SN.push(sn);  Marked[Cx][Cy]=true;};
     }
  }

int main()
{
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
 StartProcess();
 Found=(Sx==Ex) && (Sy==Ey);
 while (not Found)
   {
      int x = X.front();  X.pop();
      int y = Y.front();  Y.pop();
      int sn=SN.front(); SN.pop();
      sn++;
      PutAll(x,y,sn,Found);
   }
 cout << SN.back(); }


Powered by Atlassian Confluence, the Enterprise Wiki. (Version: http://www.atlassian.com/software/confluence Build:#2.6.1 916) - Ошибка/новая особенность - Свяжитесь с Администраторами