题解——single(二次扫描+数学)
*暴力BFS真出奇迹了 *
题面
Description
冬眠了五年，光终于从梦中醒来。
千咲、要，大家都在。
隐约记得“昨天”的海船祭，爱花意外成为贡女，沉入海底。
海面冰封，却有丝丝暖流在冰面之下涌动。
此时，爱花沉睡在祭海女神的墓地。她的胞衣在一点点脱落，化作一簇簇暖流，夹杂着她的感情，向海面上涌去。
爱花，你在哪里？
五年之后，纺已经成为海洋学研究科的大学生。
在纺的帮助下，光得知了海面下海流的情况。
纺告诉光，暖流一旦产生，就会不断地向四周扩散，直到遇到海中的岩石。
红腹海牛，快告诉光，爱花在哪里。
纺帮你绘制了一张海流情况图，长度为N，宽度为M。
然后私有题面隐藏了
Input
海图
Output
海花的位置
in.1
5 5
YYYHB
YYHHH
YHHXB
BBHBB
BBBBB
out.1
2 3
数据范围与约定
对于30%的数据，n,m<=10
对于70%的数据，n,m<=100
对于100%的数据，n,m<=300
思路
主要思路
对H暴力BFS扫，数据水，只要最后同时扫完H，那么枚举的该点合法，否则不合法。
细节
实际复杂度远低于 N^4 大概只要 N^3 多一点
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 305 ;
char s[ MAXN ] ;
int to[ 4 ][ 2 ] = { { 0 , 1 } , { 0 , -1 } , { 1 , 0 } , { -1 , 0 } } ;
int N , M , a[ MAXN ][ MAXN ] , dfn[ MAXN ][ MAXN ] , vis[ MAXN ][ MAXN ] , tot = 0 ;
bool used[ MAXN ][ MAXN ] ;//used记录ans
queue< pair< int , int > >q ;//广搜
void Init(){
scanf("%d%d",&N,&M) ;
for( int i = 1 ; i <= N ; ++i ){
scanf("%s",s);
for( int j = 1 ; j <= M ; ++j )
if( s[ j-1 ] == 'H' )a[ i ][ j ] = 1 , tot++ ;//暖流
else if( s[ j-1 ] == 'B' )a[ i ][ j ] = 2 ;//海洋
else if( s[ j-1 ] == 'Y' )a[ i ][ j ] = 3 ;//沙滩
else if( s[ j-1 ] == 'X' )a[ i ][ j ] = 4 ;//暗礁
}
}
void lis(){
for( int i = 1 ; i <= N ; ++i )
for( int j = 1 ; j <= M ; ++j )
if( a[ i ][ j ] == 1 ){
cout<<i<<" "<<j; return ;
}
}
bool bfs( int xxx , int yyy ){
while( !q.empty() )q.pop() ;
q.push( make_pair( xxx , yyy ) ) ;
memset( vis ,0 , sizeof(vis) ) ;
vis[ xxx ][ yyy ] = 1 ;
int num = 1 ;
while( !q.empty() ){
int x = q.front().first , y = q.front().second ; q.pop() ;
if( vis[ x ][ y ] != dfn[ x ][ y ] )used[ x ][ y ] = false ;
//cout<<x<<" "<<y<<endl ;
for( int i = 0 ; i < 4 ; ++i ){
int xx = x+to[ i ][ 0 ] , yy = y + to[ i ][ 1 ] ;
if(xx<=M&&xx>0&&yy>0&&yy<=M&&a[xx][yy]!=3&&a[xx][yy]!=4&&vis[xx][yy]==0){
if(a[xx][yy]==1)
{
num++;
vis[xx][yy]=1;
q.push(make_pair(xx,yy));
if(num==tot)
return 1;
}
else return 0;
}
}
}
return 0 ;
}
int main(){
freopen("calm.in","r",stdin) ;
freopen("calm.out","w",stdout) ;
Init() ;
if( tot == 0 ){cout<<"-1";return 0 ;}
if( tot == 1 ){lis(); return 0 ;}
for( int i = 1 ; i <= N ; ++i )
for( int j = 1 ; j <= M ; ++j )
if( a[ i ][ j ] == 1 )
if( bfs( i , j ) ){
cout<<i<<" "<<j;
return 0 ;
}
cout<<-1 ;
return 0 ;
}
备注：标程有锅，各位注意