srm 700 div2 medium XMarksTheSpot

問題

問題概要

Oは宝を含んでいる場所。?は宝を含んでいるかどうかがわからない場所。?の場所を宝が含んでいるか含んでいないかのすべての場合について、宝が含まれる可能性のある面積を求め、その合計を求める。

解法

今回は単純にbit全探索をすればいい。?の数は20以下なのでこれでいける。実装方法は、まず、Oだけで左右上下の最大最小を求めておく。あとは、全探索のbitmaskに応じて、使用する?の位置を左右前後の最大最小に反映させることで、その場合の長方形の面積が求まる。これをすべての場合に対して行えば良い。

ミス

特になし。

コード

#include <iostream>
#include <set>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

class XMarksTheSpot{
public:
    int countArea(vector<string> board){
        int l = INF, r = 0;
        int u = INF, d = 0;
        int cnt = 0;
        vector<pair<int, int> > memo;
        rep(i, board.size()){
            rep(j, board[i].size()){
                if(board[i][j] == 'O'){
                    l = min(l, j);
                    r = max(r, j);
                    u = min(u, i);
                    d = max(d, i);
                }else if(board[i][j] == '?'){
                    memo.push_back(make_pair(i, j));
                    cnt++;
                }
            }
        }
        
        int ans = 0;
        for (int mask = 0; mask < (1 << cnt); ++mask){
            int nl = l, nr = r, nu = u, nd = d;
            for (int i = 0; i < cnt; ++i){
                if((mask & (1 << i)) != 0){
                    nl = min(nl, memo[i].second);
                    nr = max(nr, memo[i].second);
                    nu = min(nu, memo[i].first);
                    nd = max(nd, memo[i].first);
                }
            }
            ans += (nr - nl + 1) * (nd - nu + 1);
        }
        return ans;
    }
};

int main(void){
    XMarksTheSpot xt;
    int n; cin >> n;
    vector<string> s;
    rep(i, n){
        string t; cin >> t;
        s.push_back(t);
    }
    printf("%d\n", xt.countArea(s));
    return 0;

}