青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

30 15 
.............................. 
..............................
 ...............*.............. 
...*****......****............ 
...*X***.....**X***...........
 ...*****....***X**............
 ...***X*.....****.............
 ...*****.......*..............
 ..............................
 ........***........******.....
 .......**X****.....*X**X*.....
 ......*******......******..... 
.....****X**.......*X**X*..... 
........***........******..... 
..............................
比如上面這個30 * 15的圖片里面，一共有四個區(qū)域，*作為區(qū)域的底色，然后是求區(qū)域里面有多少個X的塊。這個題單純dfs的話，很沒辦法，因為無法一次性把連接在一起的X都搜索了。比如，
5 5
XXX*X 
XXX*X 
..... 
X***X 
XX*** 
的時候，dfs很明顯就會出現(xiàn)問題，因為會先離開X塊，再次回到X塊，計數(shù)就會出現(xiàn)問題了。因此只能遇到X的時候，進行一次bfs，將與其相連接的X全部搜索掉。。。并且找到與當前X塊相連接的一個*的位置，如果有這樣的位置，就繼續(xù)進行dfs。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

int nW, nH;
char szData[100][100];
bool bVisit[100][100];
int nNum;
int nDice[100];
int nAdd[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

bool IsPosOk(int i, int j)
{
    return i >= 0 && i < nH && j >= 0 && j < nW;
}

struct POS
{
    int nI;
    int nJ;
};

bool Bfs(int& nI, int& nJ)
{
    bool bRet = false;
    queue<POS> qp;
    POS pos = {nI, nJ};
    int i = nI, j = nJ;

    qp.push(pos);
    while (qp.empty() == false)
    {
        POS head = qp.front();
        qp.pop();

        for (int m = 0; m < 4; ++m)
        {
            int nNextI = head.nI + nAdd[m][0];
            int nNextJ = head.nJ + nAdd[m][1];

            if (IsPosOk(nNextI, nNextJ) && bVisit[nNextI][nNextJ] == false)
            {
                if (szData[nNextI][nNextJ] == 'X')
                {
                    bVisit[nNextI][nNextJ] = true;
                    POS pos = {nNextI, nNextJ};
                    qp.push(pos);
                }
                else if (szData[nNextI][nNextJ] == '*')
                {
                    bRet = true;
                    nI = nNextI;//   這里是返回新的dfs位置
                    nJ = nNextJ;
                }
            }
        }
    }
    
    return bRet;
}

void dfs(int i, int j, int nNum)
{
    bVisit[i][j] = true;
    if (szData[i][j] == 'X')
    {
        nDice[nNum]++;
        bool bDfs = Bfs(i, j);//擴散掉當前連通的所有'X'
        if (bDfs == false)
        {
            return;
        }
        else
        {
            dfs(i, j, nNum);
        }
    }

    for (int m = 0; m < 4; ++m)
    {
        int nNextI = i + nAdd[m][0];
        int nNextJ = j + nAdd[m][1];

        if (IsPosOk(nNextI, nNextJ) && bVisit[nNextI][nNextJ] == false
                && szData[nNextI][nNextJ] != '.')
        {
            dfs(nNextI, nNextJ, nNum);
        }
    }
}

int main()
{
    int nCases = 1;

    while (scanf("%d%d", &nW, &nH), nW + nH)
    {
        for (int i = 0; i < nH; ++i)
        {
            scanf("%s", szData[i]);
        }
        memset(bVisit, false, sizeof(bVisit));
        memset(nDice, 0, sizeof(nDice));
        nNum = 0;

        for (int i = 0; i < nH; ++i)
        {
            for (int j = 0; j < nW; ++j)
            {
                if (szData[i][j] == 'X' && bVisit[i][j] == false)
                {
                    dfs(i, j, nNum);
                    nNum++;
                }
            }
        }
        sort(nDice, nDice + nNum);

        printf("Throw %d\n", nCases++);
        for (int i = 0; i < nNum; ++i)
        {
            printf("%d%s", nDice[i], i == nNum - 1 ? "\n" : " ");
        }
        printf("\n");
    }

    return 0;
}