Codeforces 363 Div2 B. One Bomb

問題

問題概要

縦横のマスが与えられる。その中に壁が含まれていて、それらを爆弾で吹き飛ばす。爆弾の効果は、爆弾を置いた列と行のすべての爆弾を吹き飛ばす。

解法

まず、列と行ごとに壁の数をメモしておく。これをしないで、毎回調べるとTLE。また、すべての壁の数をメモしておく。その後、爆弾の位置を決めて、同じ行と列の壁の合計数がすべての壁の数と一致したら、その座標が答えとなる。

ミス

特になし。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
    int h, w; scanf("%d %d", &h, &w);
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    int x, y;
    int cnt = 0;//壁の総数を入れる
    rep(i, h)rep(j, w){
        if(s[i][j] == '*') cnt++;
    }
    //行ごと和を取る
    vector<int> sumh(h, 0);
    rep(i, h){
        rep(j, w){
            if(s[i][j] == '*') sumh[i]++;
        }
    }
    //列ごとに和を取る
    vector<int> sumw(w, 0);
    rep(i, w){
        rep(j, h){
            if(s[j][i] == '*') sumw[i]++;
        }
    }

    bool flag = false;
    //爆弾を置く場所を全探索する
    for (int i = 0; i < h; ++i){
        for (int j = 0; j < w; ++j){
            int now = sumh[i] + sumw[j];
            if(s[i][j] == '*') now--;
            if(now == cnt){
                y = j + 1; x = i + 1;
                printf("YES\n");
                printf("%d %d\n", x, y);
                flag = true;
                return 0;
            }
        }
    }

    if(flag == false){
        printf("NO\n");
    }

    return 0;
}