ural 1119 Metro

http://acm.timus.ru/problem.aspx?space=1&num=1119

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <cmath>

 #include <algorithm>

 #define maxn 1010

 using namespace std;

 int head[maxn],e,n,m;

 int dir[][]={{,-},{,},{,},{-,}};

 bool vis[maxn][maxn];

 bool visi[maxn][maxn];

 double step;

 struct node

 {

     int x,y;

     double step;

 }st,st1,st2;

 void bfs(node st)

 {

     queue<node>q;

     st.step=0.0;

     q.push(st);

     memset(visi,false,sizeof(visi));

     visi[st.x][st.y]=true;

     while(!q.empty())

     {

         st1=q.front();

         q.pop();

         if(st1.x==m&&st1.y==n) {step=st1.step;return;}

         for(int i=; i<; i++)

         {

             int xx=st1.x+dir[i][];

             int yy=st1.y+dir[i][];

             if(xx>=&&xx<=m&&yy>=&&yy<=n&&!visi[xx][yy])

             {

                 st2.step=st1.step+100.0;

                 visi[xx][yy]=true;

                 st2.x=xx;

                 st2.y=yy;

                 q.push(st2);

             }

         }

         if(vis[st1.x+][st1.y+]&&st1.x+<=m&&st1.y+<=n&&st1.x+>=&&st1.y+>=)

         {

             vis[st1.x+][st1.y+]=true;

             st2.x=st1.x+;

             st2.y=st1.y+;

             st2.step=st1.step+sqrt()*100.0;

             q.push(st2);

         }

     }

 }

 int main()

 {

     int k,a,b;

     step=;

     scanf("%d%d",&n,&m);

     scanf("%d",&k);

     memset(vis,false,sizeof(vis));

     for(int i=; i<=k; i++)

     {

         scanf("%d%d",&a,&b);

         vis[b][a]=true;

     }

     st.x=;

     st.y=;

     bfs(st);

     printf("%.0lf\n",step);

     return ;

 }