oj.uz

Submission #1117362

# Submission time Handle Problem Language Result Execution time Memory
1117362 2024-11-23T12:03:37 Z Tai_xiu Zoo (COCI19_zoo) C++14
110 / 110
 106 ms 109796 KB 
#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.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100012 KB Output is correct
2 Correct 47 ms 99916 KB Output is correct
3 Correct 46 ms 100168 KB Output is correct
4 Correct 46 ms 100176 KB Output is correct
5 Correct 51 ms 100424 KB Output is correct
6 Correct 55 ms 100424 KB Output is correct
7 Correct 51 ms 100324 KB Output is correct
8 Correct 54 ms 100424 KB Output is correct
9 Correct 59 ms 100424 KB Output is correct
10 Correct 59 ms 100436 KB Output is correct
11 Correct 58 ms 100424 KB Output is correct
12 Correct 56 ms 100424 KB Output is correct
13 Correct 58 ms 100424 KB Output is correct
14 Correct 54 ms 100424 KB Output is correct
15 Correct 56 ms 100432 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100012 KB Output is correct
2 Correct 47 ms 99916 KB Output is correct
3 Correct 46 ms 100168 KB Output is correct
4 Correct 46 ms 100176 KB Output is correct
5 Correct 51 ms 100424 KB Output is correct
6 Correct 55 ms 100424 KB Output is correct
7 Correct 51 ms 100324 KB Output is correct
8 Correct 54 ms 100424 KB Output is correct
9 Correct 59 ms 100424 KB Output is correct
10 Correct 59 ms 100436 KB Output is correct
11 Correct 58 ms 100424 KB Output is correct
12 Correct 56 ms 100424 KB Output is correct
13 Correct 58 ms 100424 KB Output is correct
14 Correct 54 ms 100424 KB Output is correct
15 Correct 56 ms 100432 KB Output is correct
16 Correct 65 ms 106808 KB Output is correct
17 Correct 62 ms 106568 KB Output is correct
18 Correct 64 ms 106872 KB Output is correct
19 Correct 68 ms 106924 KB Output is correct
20 Correct 66 ms 106568 KB Output is correct
21 Correct 99 ms 109384 KB Output is correct
22 Correct 92 ms 109384 KB Output is correct
23 Correct 94 ms 109384 KB Output is correct
24 Correct 99 ms 109796 KB Output is correct
25 Correct 98 ms 109700 KB Output is correct
26 Correct 99 ms 109404 KB Output is correct
27 Correct 106 ms 109384 KB Output is correct
28 Correct 96 ms 109384 KB Output is correct
29 Correct 105 ms 109640 KB Output is correct
30 Correct 100 ms 109640 KB Output is correct