白駿アルゴリズム1303:戦争-戦闘

11205 ワード
DFS バックアップアルゴリズム FloodFill テキストリンク

リンク


https://www.acmicpc.net/problem/1303

質問する


戦争はいつの間にか全面開戦した.最後の戦いは乱戦となり、私たちの兵士と敵国の兵士が混戦した.
しかし、あなたの兵士たちは白い服を着ていて、敵国の兵士たちは青い服を着ているので、お互いが敵なのか味方なのかを区別することができます.
問題は、同じチームの兵士が集まるほど強くなるということです.
N人が集まると、N^2の威力を発揮します.果たして今の乱戦で、誰が勝つのか.しかし、同一隊の兵士は対角線だけが隣接しているとは思えず一丸となっている.

入力


第1行は、戦場の横方向の大きさN、縦方向の大きさM(1≦N、M≦100)を与える.2列目では、M+1列にそれぞれ(X,Y)の兵士たちの服の色があり、スペースはありません.どこにも兵士がいます.△Bは青、Wは白です.

しゅつりょく


第1行はあなたの兵士の威力の和と敵国の兵士の威力の和を出力します.

入力と出力の例



解法


これは
  • の典型的なDFS上下左右探索問題である.
  • 入力のスペースのない文字列を入力し、隣接行列で表現し、dfsを回転させます.
  • 兵士によると、上下左右にN人の兵士が集まると、N^2の力が発生するため、dfs関数を変更して接続要素の個数を返し、最後に平方を行い、すべての総和出力を加えることができるという.

    • プールコード（C言語）

    // 1303번 : 전쟁 - 전투(실버 1)

#include <stdio.h>
#include <stdbool.h>

int n, m, w, b;
char a[101][101];
bool check[100][100];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int dfs(int x, int y, char c)
{
    int ret = 1;
    check[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m)
            continue;
        if (!check[nx][ny] && a[nx][ny] == c)
            ret += dfs(nx, ny, c);
    }
    return ret;
}

int main()
{
    scanf("%d %d", &m, &n); // m: 가로 , n : 세로
    for (int i = 0; i < n; i++)
        scanf("%s", a[i]);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!check[i][j])
            {
                int k = dfs(i, j, a[i][j]);
                if (a[i][j] == 'W')
                    w += k * k;
                else
                    b += k * k;
            }
        }
    }
    printf("%d %d\n", w, b);
    return 0;
}
    [TIL]10月29日:Flask Errno 48
    ViewdispatchTouchEventソース分析(三)