'B'為fighter，'P'為enemy，'*'圍起來的範圍內為一個sector，sector的編號由左至右由上至下，要計算每個sector裡面有幾組fighter和幾組enemy，如果fighter和enemy面對面的話，表示有2個group在fighting position。
面對面的情況只會各有一組，
BBB
PP
不會有底下這種情況
BBB
PP
BBB
想法：
用DFS_1來走遍該sector，如果碰到'B'或'P'則用DFS_2走遍該group，並確認有沒有碰到另一個group。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
沒有留言:
張貼留言