[UVa] 10592 Freedom Fighter.cpp

#include <cstdio>
using namespace std;

int n;
int fighter, enemy, fighting_group;
char grid[51][51];
const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

bool DFS_2(char, int ,int);
void DFS_1(int i, int j, int &fighter, int &enemy)  // DFS_1用來走遍'*',如果遇到'B'或'P'則進入DFS_2
{
    grid[i][j] = '.';
    for (int x = 0; x < 4; ++x) {
        int nxt_i = i + direction[x][0];
        int nxt_j = j + direction[x][1];
        if (nxt_i < 0 || nxt_i >= n || nxt_j < 0 || nxt_j >= n) continue;

        if (grid[nxt_i][nxt_j] == 'B') {
            ++fighter;
            if (DFS_2('B', nxt_i, nxt_j)) fighting_group += 2;
        }
        if (grid[nxt_i][nxt_j] == 'P') {
            ++enemy;
            if (DFS_2('P', nxt_i, nxt_j)) fighting_group += 2;
        }
        if (grid[nxt_i][nxt_j] == '*')
           DFS_1(nxt_i, nxt_j, fighter, enemy);
    }
}
bool DFS_2(char C, int i, int j) //用來走遍'B'或'P'並確認是否有碰到另一個group(面對面)
{
    grid[i][j] = '*';
    bool another_group = 0;
    bool touch_another = 0;
    for (int x = 0; x < 4; ++x) {
        int nxt_i = i + direction[x][0];
        int nxt_j = j + direction[x][1];
        if (nxt_i < 0 || nxt_i >= n || nxt_j < 0 || nxt_j >= n) continue;

        if (C == 'B' && grid[nxt_i][nxt_j] == 'P' ||
            C == 'P' && grid[nxt_i][nxt_j] == 'B') another_group = 1;

        if (grid[nxt_i][nxt_j] == C)
            another_group = DFS_2(C, nxt_i, nxt_j);
        if (another_group == 1) touch_another = 1;
    }
    return touch_another;
}
int main()
{
  //  freopen("input.txt","rt",stdin);
    while (scanf("%d", &n) && n) {
        for (int i = 0; i < n; ++i)
            scanf("%s", grid[i]);
        int sector = 1;
        fighting_group = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] != '.') {
                    fighter = 0;
                    enemy = 0;
                    if (grid[i][j] == 'B') {++fighter; if (DFS_2('B', i, j)) fighting_group += 2;}
                    if (grid[i][j] == 'P') {++enemy; if (DFS_2('P', i, j)) fighting_group += 2;}
                    DFS_1(i, j, fighter, enemy);
                    printf("Sector #%d: contain %d freedom fighter group(s) & %d enemy group(s)\n",
                           sector++, fighter, enemy);
                }
            }
        }
        printf("Total %d group(s) are in fighting position.\n\n", fighting_group);
    }
    return 0;
}