Submission #747290

#	Time	Username	Problem	Language	Result	Execution time	Memory
747290		Trunkty	Zoo (COCI19_zoo)	C++14	110 / 110	67 ms	43556 KiB

zoo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int r,c,ans;
char arr[1005][1005];
vector<pair<int,int>> bfs[1000005];
int best[1005][1005];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >> arr[i][j];
        }
    }
    best[1][1] = 1;
    bfs[1].push_back({1,1});
    for(int i=1;i<=r*c;i++){
        if(bfs[i].size()>0){
            ans = i;
        }
        for(int j=0;j<bfs[i].size();j++){
            int x = bfs[i][j].first, y = bfs[i][j].second;
            if(x!=1 and arr[x-1][y]!='*' and !best[x-1][y]){
                if(arr[x-1][y]!=arr[x][y]){
                    best[x-1][y] = best[x][y]+1;
                    bfs[best[x-1][y]].push_back({x-1,y});
                }
                else{
                    best[x-1][y] = best[x][y];
                    bfs[best[x-1][y]].push_back({x-1,y});
                }
            }
            if(x!=r and arr[x+1][y]!='*' and !best[x+1][y]){
                if(arr[x+1][y]!=arr[x][y]){
                    best[x+1][y] = best[x][y]+1;
                    bfs[best[x+1][y]].push_back({x+1,y});
                }
                else{
                    best[x+1][y] = best[x][y];
                    bfs[best[x+1][y]].push_back({x+1,y});
                }
            }
            if(y!=1 and arr[x][y-1]!='*' and !best[x][y-1]){
                if(arr[x][y-1]!=arr[x][y]){
                    best[x][y-1] = best[x][y]+1;
                    bfs[best[x][y-1]].push_back({x,y-1});
                }
                else{
                    best[x][y-1] = best[x][y];
                    bfs[best[x][y-1]].push_back({x,y-1});
                }
            }
            if(y!=c and arr[x][y+1]!='*' and !best[x][y+1]){
                if(arr[x][y+1]!=arr[x][y]){
                    best[x][y+1] = best[x][y]+1;
                    bfs[best[x][y+1]].push_back({x,y+1});
                }
                else{
                    best[x][y+1] = best[x][y];
                    bfs[best[x][y+1]].push_back({x,y+1});
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

zoo.cpp: In function 'int main()':
zoo.cpp:26:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j=0;j<bfs[i].size();j++){
      |                     ~^~~~~~~~~~~~~~

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