Codeforces Round #363 (Div. 2) B. One Bomb —— 技巧

题目链接：http://codeforces.com/contest/699/problem/B

题解：

首先统计每行每列出现‘*’的次数，以及‘*’出现的总次数，得到r[n]和c[m]数组，以及sum,。然后再枚举每一个格子（O(n^2)枚举，反正输入都是枚举的）。

对于每一个格子s[i][j]：

1.如果它是‘*’， 那么当 r[i] + c[j] - 1 = sum 时， 表明炸弹放在这个位置可以炸掉所有的墙。

2.如果它是‘.’， 那么当 r[i] + c[j] = sum 时， 表明炸弹放在这个位置可以炸掉所有的墙。

这个规律还是要画图才比较好找出来的……

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ms(a, b)  memset((a), (b), sizeof(a))
#define eps 0.0000001
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int maxn = 200000+10;

int n,m;
char s[1005][1005];
int r[1005], c[1005];

void init()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i<=n; i++)
        scanf("%s",s[i]+1);

    ms(c,0);
    ms(r,0);
}

void solve()
{
    int sum = 0;
    for(int i = 1; i<=n; i++)
    for(int j = 1; j<=m; j++)
    if(s[i][j] == '*')
        sum++, r[i]++, c[j]++;

    int B = 0, x, y;
    for(int i = 1; i<=n; i++)
    for(int j = 1; j<=m; j++)
    {
        int tmp = r[i]+c[j];
        if(s[i][j]=='*')
            tmp--;

        if(tmp==sum)
        {
            B = 1;
            x = i; y = j;
            break;
        }
    }

    if(B)
        printf("YES
%d %d
",x,y);
    else
        puts("NO");
}

int main()
{
//    int T;
//    scanf("%d",&T);
//    while(T--)
    {
        init();
        solve();
    }
    return 0;
}