Submission #1117362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117362		Tai_xiu	Zoo (COCI19_zoo)	C++14	110 / 110	106 ms	109796 KiB

zoo

#include<bits/stdc++.h>
using namespace std;

int dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;



using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<

typedef long long llint;

const int MAXN = 5005;

const int dr[] = {1, 0, -1, 0};
const int ds[] = {0, 1, 0, -1};

/*
5 4
GGWW
GWWW
GWYY
GGWG
YGGW
*/
string grid[MAXN];

int R, S, comp_cnt;
int f[MAXN][MAXN];
int vis[MAXN][MAXN];
inline bool inside(const int & r, const int & s) {
  return r >= 0 && r < R && s >= 0 && s < S;
}

struct item
{
    int x,y;
    item(){}
    item(int _x,int _y)
    {
        x=_x;
        y=_y;

    }
};
signed main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  cin>>R>>S;
  for (int i = 0; i < R; ++i)
    cin>>grid[i];
if (grid[0][0]!=grid[R-1][S-1]){
    cout<<-1;
    return 0;
}
  deque<item> Q;
  memset(f,-1,sizeof f);
  Q.push_front({0,0});
  f[0][0]=1;
//  vis[0][0]=1;
  int sol = 0;
  while (!Q.empty()) {
    auto curr = Q.front(); Q.pop_front();
    int x=curr.x;
    int y=curr.y;
    if (vis[x][y]) continue;
    vis[x][y]=1;
    for (int k=0;k<4;k++){
        int i = x + dr[k];
        int j = y + ds[k];
        int tam=0;
        if (!inside(i,j) || grid[i][j]=='*') continue;
        if (grid[i][j]!=grid[x][y]) tam=1;
        if ( f[i][j] > f[x][y] + tam || f[i][j]==-1) {
            f[i][j]=f[x][y] + tam;
            if (tam==1) Q.push_back(item(i,j));
            else Q.push_front(item(i,j));
        }
    }
  }
  for (int i=0;i<R;i++){
    for (int j=0;j<S;j++) sol=max(sol,f[i][j]);
  }
  cout<<sol;
  return 0;
}

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