jzoj3319-凯发k8官方网

---

题目大意

一个$n\ast m$的雪地，有两种动物$r$和$f$会在雪地上留下$r$和$f$的脚印(只可以走到相邻格子，从$(1,1)$进入$(n,m)$出来，且会覆盖掉原先的脚印)。

求至少有多少只动物经过

---

解题思路

首先我们知道$(1,1)$所在的联通块必定是最后一只经过的动物，因为至少所以我们优先选择整个联通块作为最后一只动物。

然后由这个联通块开始向外扩展另一种脚印的联通块，之后不停扩展直到扩完为止。

---

$code$

#pragma gcc optimize(2) %:pragma gcc optimize(3) %:pragma gcc optimize("ofast") %:pragma gcc optimize("inline") #include #include #include #include #include using namespace std; const int n=4001; const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; int n,m,ans,v[n][n]; int qx[n*n],qy[n*n],l=1,r; char c[n][n],z; queue<int> shix,shiy; inline long long read() {char c;int f=0,d=1;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)(f<<1)c-48;while(c=getchar(),isdigit(c)) f=(f<<3)(f<<1)c-48;return d*f; } void bfs(int x,int y,char pos) {shix.push(x);shiy.push(y);while(!shix.empty()){x=shix.front();y=shiy.front();shix.pop();shiy.pop();for(int k=0;k<4;k){int zx=xdx[k],zy=ydy[k];if(zx<1||zy<1||zx>n||zy>m)continue;if(v[zx][zy]||c[zx][zy]!=pos)continue;v[zx][zy]=1;shix.push(zx);shiy.push(zy);qx[r]=zx;qy[r]=zy;}} } int main() {freopen("data.txt","r",stdin);n=read();m=read();for(int i=1;i<=n;i)gets(c[i]1);v[1][1]=qx[r]=qy[r]=1;bfs(1,1,c[1][1]);z=c[1][1];while(l<=r){ans;int r=r;if(z=='f') z='r';else z='f';for(int i=l;i<=r;i)bfs(qx[i],qy[i],z);l=r1;}cout<<ans; }

总结

以上是凯发k8官方网为你收集整理的jzoj3319-[boi2013]雪地踪迹【bfs】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。