搜尋--16

題目大概：

輸入n和m，是一個n*m的矩形，裡面由*和@組成。找出有幾組@。一組@是指，一個@符号在矩形中的八個方向上有@，那這兩個@就算一組。

思路：

就是看看這個矩形域内有幾團@。可以用深搜或廣搜，不斷查找，直到附近沒有了@ 算一組。

但要注意标記記錄@是否被計算過。

代碼：

已更新

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
    int x,y;
};
int n,m;
int dx[10]= {1,-1,0,0,1,1,-1,-1};
int dy[10]= {0,0,1,-1,1,-1,1,-1};
bool vis[120][120];
char Map[120][120];
int sum=0;
int pan(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]&&Map[x][y]=='@')
    {
        return 1;
    }
    return 0;
}

void bfs(int x,int y)
{
    queue<node>Q;
    node st;
    vis[x][y]=1;
    st.x=x;
    st.y=y;
    Q.push(st);
    while(!Q.empty())
    {
        node u=Q.front();
        Q.pop();
        for(int i=0; i<8; i++)
        {
            int xx=u.x+dx[i];
            int yy=u.y+dy[i];
            if(pan(xx,yy))
            {
                vis[xx][yy]=1;
                node v;
                v.x=xx;
                v.y=yy;
                Q.push(v);
            }
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(~scanf("%d%d",&n,&m)&&n&&m)
    {
        sum=0;
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++)
        {
            scanf("%s",Map[i]+1);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(!vis[i][j]&&Map[i][j]=='@')
                {
                    bfs(i,j);
                    sum++;
                }
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}