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