Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 1st, 2012  |  syntax: C++  |  size: 1.94 KB  |  hits: 13  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.  include <iostream>
  2. # include <cstdio>
  3. # include <queue>
  4. # include <string>
  5. # include <algorithm>
  6. # define mp make_pair
  7. # define pii pair <int, int>
  8.  
  9. using namespace std;
  10.            
  11. //'a'=97 'z'=122 '1'=49(WTF?!)
  12. queue <pii> qw;
  13. queue <int> o;
  14. int clr[10][10];
  15. pii k1;                     //0
  16. pii k2;                     //1
  17. pii k[8];
  18. int ans=-1,r[10][10];
  19.  
  20. void bfs ()
  21. {
  22.     while (!qw.empty())
  23.     {
  24.         pii z=qw.front();
  25.         int wtf=o.front();
  26.         qw.pop();
  27.         o.pop();
  28.         for (int i=0;i<8;i++)
  29.         {
  30.             if (z.first+k[i].first>0 && z.first+k[i].first<9 && z.second+k[i].second>0 && z.second+k[i].second<9)
  31.                 if (r[z.first+k[i].first][z.second+k[i].second]==-1)
  32.                 {
  33.                     pii t=mp(z.first+k[i].first,z.second+k[i].second);
  34.                     qw.push(t);
  35.                     r[t.first][t.second]=r[z.first][z.second]+1;
  36.                     clr[t.first][t.second]=wtf;    
  37.                     o.push(wtf);
  38.                 }
  39.                 else
  40.                     if (wtf!=clr[z.first+k[i].first][z.second+k[i].second])
  41.                     {
  42.                         ans=r[z.first+k[i].first][z.second+k[i].second];
  43.                         return;
  44.                     }
  45.         }
  46.     }
  47.  
  48. }
  49.  
  50. int main ()
  51. {
  52.     //freopen ("1.txt","r",stdin);
  53.    
  54.     fill (&clr[0][0],&clr[9][9],-1);
  55.     fill (&r[0][0],&r[9][9],-1);
  56.     k[0]=mp(-1,-2);
  57.     k[1]=mp(-1,2);
  58.     k[2]=mp(1,-2);
  59.     k[3]=mp(1,2);
  60.     k[4]=mp(2,-1);
  61.     k[5]=mp(2,1);
  62.     k[6]=mp(-2,-1);
  63.     k[7]=mp(-2,1);
  64.    
  65.     string pos1,pos2;
  66.     cin>>pos1>>pos2;
  67.     k1=mp(pos1[0]-96,pos1[1]-48);
  68.     k2=mp(pos2[0]-96,pos2[1]-48);
  69.  
  70.     qw.push(k1);
  71.     qw.push(k2);
  72.     r[k1.first][k1.second]=0;
  73.     r[k2.first][k2.second]=0;
  74.     o.push(0);
  75.     o.push(1);
  76.     clr[k1.first][k1.second]=0;
  77.     clr[k2.first][k2.second]=1;
  78.  
  79.     bfs();
  80.  
  81.     cout<<ans<<endl;
  82.     return 0;
  83. }
create a new version of this paste RAW Paste Data