範例程式碼 uva657

//uva657
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 50

using namespace std;

int row, col, ansNum, caseNum = 1;
int ans[MAX * MAX], pathStar[MAX][MAX], pathX[MAX][MAX];
int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
char picture[MAX][MAX];

// use DFS to check the dice point
void findX(int i, int j) {
    // DFS at leaf point
    if(pathX[i][j] == 1)
        return;

    for(int k = 0; k < 4; k++)
    {
        // out of range
        if(i + dir[k][0] < 0 || i + dir[k][0] >= row)
            continue;
        if(j + dir[k][1] < 0 || j + dir[k][1] >= col)
            continue;

        // not 'X'
        if(picture[i + dir[k][0]][j + dir[k][1]] != 'X')
            continue;

        // has find before
        if(pathX[i + dir[k][0]][j + dir[k][1]] == 1)
            continue;

        // set this point has been check
        pathX[i][j] = 1;

        // find next point
        findX(i + dir[k][0], j + dir[k][1]);
    }

    // set this point has been check
    pathX[i][j] = 1;
}

// use DFS to check the dice
void findStar(int i, int j) {
    // DFS at leaf point
    if(pathStar[i][j] == 1)
        return;

    for(int k = 0; k < 4; k++) {
        // out of range
        if(i + dir[k][0] < 0 || i + dir[k][0] >= row)
            continue;
        if(j + dir[k][1] < 0 || j + dir[k][1] >= col)
            continue;

        // not '*'
        if(picture[i + dir[k][0]][j + dir[k][1]] == '.')
            continue;

        // has find before
        if(pathStar[i + dir[k][0]][j + dir[k][1]])
            continue;

        // we need to check
        if(picture[i + dir[k][0]][j + dir[k][1]] != '.') {
            // find the dice point and use DFS to check that point
            if(picture[i + dir[k][0]][j + dir[k][1]] == 'X' && pathX[i + dir[k][0]][j + dir[k][1]] == 0) {
                // find the dice point
                ans[ansNum]++;

                // use DFS to check that dice point
                findX(i + dir[k][0], j + dir[k][1]);
            }

            // set this point has been check
            pathStar[i][j] = 1;

            // find next point
            findStar(i + dir[k][0], j + dir[k][1]);
        }
    }

    // set this point has been check
    pathStar[i][j] = 1;
}

int main() {
    // get first input
    cin >> col >> row;

    while(row != 0 && col != 0) {
        // get picture
        for(int i = 0; i < row; i++)
            cin >> picture[i];

        // initialize
        ansNum = 0;
        memset(pathStar, 0, sizeof(pathStar));
        memset(pathX, 0, sizeof(pathX));
        memset(ans, 0, sizeof(ans));

        // find how many dices (the first star position)
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(picture[i][j] != '.' && pathStar[i][j] == 0) {
                    findStar(i, j);

                    // the first 'X' haven't count
                    if(picture[i][j] == 'X')
                        ans[ansNum]++;

                    ansNum++;
                }
            }
        }

        // sort the answer
        sort(ans, ans + ansNum);

        // output the answer
        cout << "Throw " << caseNum << endl;
        for(int i = 0; i < ansNum - 1; i++)
            cout << ans[i] << ' ';
        cout << ans[ansNum - 1] << endl << endl;

        // get next input
        cin >> col >> row;
        caseNum++;
    }

    return 0;
}