首页 > 代码库 > LightOJ 1012 简单bfs,水

LightOJ 1012 简单bfs,水

1、LightOJ 1012  Guilty Prince  简单bfs

2、总结:水

题意:迷宫,求有多少位置可去

技术分享
#include<iostream>#include<cstring>#include<cmath>#include<queue>#include<algorithm>#include<cstdio>#define F(i,a,b) for (int i=a;i<=b;i++)using namespace std;#define LL long long#define INF 0x3f3f3f3fconst int N=25;struct Point{    int x,y;};char mapn[N][N];int visit[N][N];int w,h,ii,jj;int dirw[4]={0,0,1,-1};int dirh[4]={1,-1,0,0};bool charge(Point e){    if(e.x>=0&&e.x<h&&e.y>=0&&e.y<w&&!visit[e.x][e.y]&&mapn[e.x][e.y]==.)        return true;    return false;}int dfs(){    int ans=1;    Point st,en;    queue<Point>q;    st.x=ii,st.y=jj;    q.push(st);    while(!q.empty()){        st=q.front();        q.pop();        for(int i=0;i<4;i++){            en.x=st.x+dirh[i];            en.y=st.y+dirw[i];            if(charge(en)){                q.push(en);                visit[en.x][en.y]=1;                ans++;            }        }    }    return ans;}int main(){    int n;    scanf("%d",&n);    for(int cas=1;cas<=n;cas++)    {        memset(visit,0,sizeof(visit));        scanf("%d%d",&w,&h);        for(int i=0;i<h;i++){            scanf("%s",mapn[i]);  //从0开始,故下面j要注意            for(int j=0;j<w;j++){                if(mapn[i][j]==@)                    ii=i,jj=j,visit[i][j]=1;            }        }        int ans=dfs();        printf("Case %d: %d\n",cas,ans);    }    return 0;}
View Code

 

LightOJ 1012 简单bfs,水