Занятие 11

Задача

#include <vector>
#include <string>
#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;
typedef pair<int,int> ipair;
vector<vector<ipair> > from(8,vector<ipair>(8,make_pair(-1,-1)));
deque<ipair> q;
vector<string> map(8);
void add(ipair p, ipair f)
{
  if(p.first<0 || p.first>=8) return;
  if(p.second<0 || p.second>=8) return;
  if(map[p.first][p.second]=='#') return;
  if(from[p.first][p.second].first>=0) return;
  from[ p.first][p.second]=f;
  q.push_back(p);
}
int main()
{ for(int i=0;i<8;++i)
    cin>>map[i];
  q.push_back(make_pair(0,0));
  from[0][0]=make_pair(0,0);
  while(q.size()>0)
  { ipair f=q.front();
    q.pop_front();
    add(make_pair(f.first+1,f.second+2),f);
    add(make_pair(f.first-1,f.second+2),f);
    add(make_pair(f.first+1,f.second-2),f);
    add(make_pair(f.first-1,f.second-2),f);
    add(make_pair(f.first+2,f.second+1),f);
    add(make_pair(f.first-2,f.second+1),f);
    add(make_pair(f.first+2,f.second-1),f);
    add(make_pair(f.first-2,f.second-1),f);
  }
  if(from[7][7].first<0)
    cout<<"IMPOSSIBLE\n";
  else
  { ipair p=make_pair(7,7);
    while(p!=make_pair(0,0))
    {
      q.push_back(p);
      p=from[p.first][p.second];
    }
    q.push_back(p);
    cout<<(q.size()-1)<<endl;
    while(q.size()>0)
    { p=q.back();
      q.pop_back();
      cout<<(p.first+1)<<' '<<(p.second+1)<<endl;
    }
  }
}