AOJ-ICPC 2014 - 備忘録

無人島に流れ着いたがめつい男二人が奪い合い得た土地の広さを計算する問題。
一人は黒い杭で、もう一人は白い杭で囲まれた場所が自分の土地となります。
拡大隣接の話がちょっとややこしかったかな。

回答はこちら。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
  
using namespace std;
 
void check_white(int x, int y);
void check_black(int x, int y);
// map[x][y]とする。 x:↓ y:→
 
int W, H;
int issearched[50][50];
char landmap[50][50];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
// 上、左、下、右の順で探す
int nx, ny;
 
int main()
{
    while(1){
        cin >> W >> H;
        if(W == 0 && H == 0) break;
        vector<pair<int, int> > whitepost(2500);
        vector<pair<int, int> > blackpost(2500);
        int whitecnt = 0, blackcnt = 0;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                cin >> landmap[i][j];
                if(landmap[i][j] == 'W'){
                    whitepost[whitecnt] = make_pair<int, int>(i, j);
                    whitecnt++;
                } else if(landmap[i][j] == 'B'){
                    blackpost[blackcnt] = make_pair<int, int>(i, j);
                    blackcnt++;
                }
            }
        }
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                issearched[i][j] = 0;
            }
        }
        for(int i = 0; i < whitecnt; i++) check_white(whitepost[i].first, whitepost[i].second);
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                issearched[i][j] = 0;
            }
        }
        for(int i = 0; i < blackcnt; i++) check_black(blackpost[i].first, blackpost[i].second);
        int white_land = 0, black_land = 0;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if(landmap[i][j] == 'w') white_land++;
                else if(landmap[i][j] == 'b') black_land++;
            }
        }
        cout << black_land << ' ' << white_land << endl;
    }
    return 0;
}
 
void check_white(int x, int y)
{
    for(int i = 0; i < 4; i++){
        nx = x + dx[i];
        ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
        else {
            if(issearched[nx][ny] == 0){
                issearched[nx][ny] = 1;
                if(landmap[nx][ny] == '.'){
                    landmap[nx][ny] = 'w';
                    check_white(nx, ny);
                }
                 // else if(map[nx][ny] == 'w'){
                    // check_white(nx, ny);
                // }
            }
        }
    }
    return;
}
 
void check_black(int x, int y)
{
    for(int i = 0; i < 4; i++){
        nx = x + dx[i];
        ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
        else {
            if(issearched[nx][ny] == 0){
                issearched[nx][ny] = 1;
                if(landmap[nx][ny] == '.'){
                    landmap[nx][ny] = 'b';
                    check_black(nx, ny);
                } else if(landmap[nx][ny] == 'w'){
                    landmap[nx][ny] = '.';
                    check_black(nx, ny);
                }
            }
        }
    }
    return;
}

まず入力から白い杭、黒い杭のそれぞれの位置をpairを用いて記録します。
その後、深さ優先探索で杭のある場所から土地を求めていきます。
拡大接続の条件から、次に行くマス(nx, ny)がまだ調べられておらず、相手の土地でもない場合に自分の土地である印をつける。
これをまず白から始め、次に黒でやります。黒で土地を求める場合、すでに白の土地となっているかつ自分の土地にもなるはずであるマスはどちらの土地でもない'.'に戻します。
これでどのマスがどちらのものかわかったので、あとはマスの数を計算しておしまい。
~~正直に言うと解いたのが１０日くらい前だから覚えてない~~