首页 > 代码库 > HDU 1312 (BFS搜索模板题)

HDU 1312 (BFS搜索模板题)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1312

题目大意:问迷宫中有多少个点被访问。

解题思路

DFS肯定能水过去的。这里就拍了一下BFS。

然后发现自己BFS访问标记有问题,导致某些点被重复访问了。

赶紧改了一下。

 

#include "cstdio"#include "queue"#include "string"#include "cstring"#include "iostream"using namespace std;int n,m,sx,sy,map[25][25],dir[4][2]={-1,0,1,0,0,-1,0,1},cnt;bool vis[25][25];struct status{    int x,y;    status(int x,int y):x(x),y(y) {}};void bfs(int x,int y){    queue<status> Q;    Q.push(status(sx,sy));    vis[sx][sy]=true;    while(!Q.empty())    {        cnt++;        status t=Q.front();Q.pop();        for(int s=0;s<4;s++)        {            int X=t.x+dir[s][0],Y=t.y+dir[s][1];            if(vis[X][Y]||X<0||X>n||Y<0||Y>m||!map[X][Y]) continue;            vis[X][Y]=true;            Q.push(status(X,Y));        }    }}int main(){    //freopen("in.txt","r",stdin);    ios::sync_with_stdio(false);    string tt;    while(cin>>m>>n&&n)    {        cnt=0;        memset(vis,0,sizeof(vis));        for(int i=1;i<=n;i++)        {            cin>>tt;            for(int j=0;j<tt.size();j++)            {                if(tt[j]==#) map[i][j+1]=0;                if(tt[j]==.) map[i][j+1]=1;                if(tt[j]==@) {map[i][j+1]=2;sx=i;sy=j+1;}            }        }        bfs(sx,sy);        cout<<cnt<<endl;    }}

 

18694832014-10-14 14:49:59Accepted131215MS292K1246 BC++Physcal

HDU 1312 (BFS搜索模板题)