当前位置: 代码迷 >> 综合 >> Codeforces #363 One Bomb
  详细解决方案

Codeforces #363 One Bomb

热度:37   发布时间:2023-12-06 03:18:43.0

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



很悲催的一题啊,小编刚刚把这道题锁住就想起了一个错误点,虽然靠着错误点hack了很多人,但是仍然抵不上过不了终端的痛。

首先小编就先来介绍一下一个错误的做法,统计出现最多的横坐标和纵坐标,然后以这个为炸弹,反过来看有没有点不在这个炸弹范围内来判断可不可以。这种做法乍一看是对的,但是有一种特殊的数据可以把它卡掉:

3 3

*..

.*.

...

这组数据显然是可以的,但是用统计来做的话肯定就是错的,所以这组数据可以把它嫁掉,当然其实这种做法加一个小小的特判就能过,。只要特判下有没有这种情况的发生就好了。

现在小编再来介绍一种另外一种做法,那就是直接枚举每一个位置,判断其范围内是否有所有的墙壁,当然只要统计就好了,不用真的去延伸算。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000+5;
char G[maxn][maxn];
int x[maxn], y[maxn],cnt;
int main()
{int n,m;scanf("%d%d", &n,&m);for(int i=0; i<n; i++)scanf("%s", G[i]);for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(G[i][j] == '*'){x[i]++;y[j]++;cnt++;}for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(x[i]+y[j]-(G[i][j] == '*') == cnt){printf("YES\n%d %d\n", i+1,j+1);return 0;}printf("NO\n");
}