bzoj1627 / P2873 [USACO07DEC]泥水坑Mud Puddles

bfs入门。

对于坐标为负的情况，我们可以给数组下标加上$abs(min(minx,miny))$转正（根据题意判断）

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #define re register

 using namespace std;

 #define M 502

 const int d1[]={,,,-};

 const int d2[]={,,-,};

 struct node{int x,y,t;}; queue <node> h;

 int tx,ty,n; bool vis[M*+][M*+];

 int main(){

     scanf("%d%d%d",&tx,&ty,&n); tx+=M;ty+=M; int q1,q2;

     for(int i=;i<=n;++i) scanf("%d%d",&q1,&q2),vis[q1+M][q2+M]=;

     h.push((node){M,M,}); vis[M][M]=;

     while(!h.empty()){

         node u=h.front(); h.pop();

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

             int r1=u.x+d1[i],r2=u.y+d2[i];

             if(vis[r1][r2]) continue;

             if(r1==tx&&r2==ty){

                 printf("%d",u.t+);

                 return ;

             }h.push((node){r1,r2,u.t+}),vis[r1][r2]=;

         }

     }

 }