제출 #1308651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308651		mrasool1665	Zoo (COCI19_zoo)	C++20	110 / 110	47 ms	11344 KiB

zoo

//MRasool Kheyri 
//Iran , BandarAbbas
//16/10/1404
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define el '\n'
#define lid id<<1
#define rid lid|1
#define mid (l+r)/2 
const ll maxn = 1e3 + 100 ;
const ll mod = 1e9 + 7 ;
const ll oo = 1e18 + 100 ;
ll n , m , dis[maxn][maxn] ;
string s[maxn] ;
void solve(){
    cin>>n>>m ;
    for(ll i = 0 ; i < n ; i++){
        cin>>s[i] ;
    }
    for(ll i = 0 ; i < n ; i++){
        for(ll j = 0 ; j < m ; j++){
            dis[i][j] = oo ;
        }
    }
    deque<pair<pair<ll,ll>,ll>> q ;
    q.push_back({{0,0},0}) ;
    while(q.size()){
        ll x = q.front().first.first , y = q.front().first.second , h = q.front().second ;
        q.pop_front() ;
        if(dis[x][y] < oo){continue;}
        dis[x][y] = h ;
        if(x != 0 && s[x-1][y] != '*' && dis[x-1][y] == oo){
            if(s[x][y] == s[x-1][y]){
                q.push_front({{x-1,y},h}) ;
            }
            else{
                q.push_back({{x-1,y},h+1}) ;
            }
        }
        if(y != 0 && s[x][y-1] != '*' && dis[x][y-1] == oo){
            if(s[x][y] == s[x][y-1]){
                q.push_front({{x,y-1},h}) ;
            }
            else{
                q.push_back({{x,y-1},h+1}) ;
            }
        }
        if(x != n-1 && s[x+1][y] != '*' && dis[x+1][y] == oo){
            if(s[x][y] == s[x+1][y]){
                q.push_front({{x+1,y},h}) ;
            }
            else{
                q.push_back({{x+1,y},h+1}) ;
            }
        }
        if(y != m-1 && s[x][y+1] != '*' && dis[x][y+1] == oo){
            if(s[x][y] == s[x][y+1]){
                q.push_front({{x,y+1},h}) ;
            }
            else{
                q.push_back({{x,y+1},h+1}) ;
            }
        }
    }
    ll ans = 0 ;
    for(ll i = 0 ; i < n ; i++){
        for(ll j = 0 ; j < m ; j++){
            if(dis[i][j] != oo){
                ans = max(ans,dis[i][j]) ;
            }
        }
    }
    ans++ ;
    cout<<ans<<el ;
    return ;
}
int main(){
    //ios_base::sync_with_stdio(0) , cin.tie(nullptr) , cout.tie(nullptr) ;
    ll t = 1 ;
    //cin>>t ;
    while(t--){
        solve() ;
    }
    return 0 ;
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65