Untitled
unknown
plain_text
3 years ago
2.3 kB
11
Indexable
#include<bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define pb push_back
#define mp make_pair
#define mem(x,i) memset(x,i,sizeof(x))
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define fileout freopen("output.txt","w",stdout)
#define filein freopen("input.txt","r",stdin)
#define mod 1000000007
#define INF 1000000000
#define INF18 1e18
#define for1(i,n) for( int i = 1 ; i<=n ; i++ )
#define for0(i,n) for( int i = 0 ; i<n ; i++ )
typedef long long ll;
const char nl = '\n';
#define MAX 1000
#define pii pair< int , int >
using namespace std;
int fx[] = { 1, -1, 0, 0 };
int fy[] = { 0, 0, 1, -1 };
char cell[100][100];
int dis[100][100];
int vis[100][100];
map < pair<ll,ll> , pair<ll,ll> > parent;
int row, col;
bool found = false;
void DFS ( int sx, int sy, int cyclen )
{
vis[sx][sy] = -1 ;
for( ll k = 0 ; k<4 ; k++ )
{
ll tx = sx + fx[k];
ll ty = sy + fy[k];
if( tx >= 0 && tx<row && ty >= 0 && ty<col )
{
if( cell[tx][ty] == cell[sx][sy] )
{
if( vis[tx][ty] == 0 )
{
parent[{tx,ty}] = make_pair(sx,sy);
DFS( tx,ty, cyclen+1 );
}
else if( parent[{sx,sy}] != make_pair(tx,ty) && vis[tx][ty] == -1 )
{
if( cyclen>=4)
{
found = true;
break;
}
}
}
}
}
vis[sx][sy] = 1;
}
int main()
{
FastIO;
cin>>row>>col;
for( ll i = 0 ; i<row ; i++ )
{
for( ll j = 0; j<col ; j++ )
{
cin>>cell[i][j];
}
}
for( ll i = 0 ; i<row ; i++ )
{
for( ll j = 0; j<col ; j++ )
{
if( vis[i][j]==0 )
{
DFS( i,j,1);
}
if( found )
{
cout<<"Yes"<<endl;
return 0;
}
}
}
cout<<"No"<<endl;
return 0;
}
Editor is loading...