bzoj4512[Usaco2016 Jan] Build Gates

bzoj4512[Usaco2016 Jan] Build Gates

题意：

某人从农场的(0,0)出发，沿边界到处乱走，走过的地方会留下栅栏，等走完后问要在多少个栅栏上开门才能使整个农场连通，最多走1000步。

题解：

我的代码比别人的都长~我的做法是先算出最左/最下可能会走到哪里，然后变换一下坐标系（实际是是改变出发起点），然后记录哪个格子的上下左右被栅栏堵了，最后做一下floodfill，输出连通块数-1。注意还要把有栅栏区域的外圈格子也算进去，因为它们代表了有栅栏区域外的广大地区（这个人的农场是无限大的）。

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 using namespace std;

 bool unok[][][],vis[][]; int mx,my,tot,n;

 char opt[];

 void dfs(int x,int y){

     vis[x][y]=;

     if(y!=&&!unok[x][y][]&&!vis[x][y-])dfs(x,y-);

     if(x!=mx&&!unok[x][y][]&&!vis[x+][y])dfs(x+,y);

     if(y!=my&&!unok[x][y][]&&!vis[x][y+])dfs(x,y+);

     if(x!=&&!unok[x][y][]&&!vis[x-][y])dfs(x-,y);

 }

 int main(){

     scanf("%d",&n); int x=,y=; scanf("%s",opt);

     inc(i,,n-){if(opt[i]=='W')y++;if(opt[i]=='S')x++;}

     memset(unok,,sizeof(unok)); mx=my=;

     inc(i,,n-){

         if(opt[i]=='N'){

             unok[x][y][]=; unok[x][y-][]=; x++; mx=max(mx,x);

         }

         if(opt[i]=='S'){

             unok[x-][y][]=; unok[x-][y-][]=; x--;

         }

         if(opt[i]=='W'){

             unok[x][y-][]=; unok[x-][y-][]=; y--;

         }

         if(opt[i]=='E'){

             unok[x][y][]=; unok[x-][y][]=; y++; my=max(my,y);

         }

     }

     memset(vis,,sizeof(vis)); tot=;

     inc(i,,mx)inc(j,,my)if(!vis[i][j])tot++,dfs(i,j);

     printf("%d",tot-);

     return ;

 }

20160517