fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define DEBUG(x) cerr << "DEBUG: " << x << "\n";
  4. #define vv(x) vector<vector<x>>
  5.  
  6. using namespace std;
  7.  
  8. int h, w;
  9.  
  10. int dfs(const vv(char)& adj, vv(int)& visited, const pair<int, int>& cur_pos, int dist) {
  11.         int i = cur_pos.first, j = cur_pos.second;
  12.         char cur = adj[i][j];
  13.         char target = (((cur - 'A') + 1) % 26) + 'A';
  14.         //DEBUG("current data: " << x << y << cur)
  15.         //DEBUG("target is: " << target)
  16.  
  17.         if(visited[i][j] != -1) return visited[i][j];
  18.  
  19.         // step in all directions
  20.         vector<pair<int, int>> step;
  21.         step.push_back(make_pair(i+1, j));
  22.         step.push_back(make_pair(i+1, j+1));
  23.         step.push_back(make_pair(i+1, j-1));
  24.         step.push_back(make_pair(i, j+1));
  25.         step.push_back(make_pair(i, j-1));
  26.         step.push_back(make_pair(i-1, j));
  27.         step.push_back(make_pair(i-1, j+1));
  28.         step.push_back(make_pair(i-1, j-1));
  29.  
  30.         int max_dist = dist;
  31.         for(const auto& pr: step) {
  32.                 int ni = pr.first, nj = pr.second;
  33.                 if(ni >= h || ni < 0) continue;
  34.                 if(nj >= w || nj < 0) continue;
  35.                 //DEBUG("current step: " << nx << ", " << ny)
  36.                 if(adj[ni][nj] == target) {
  37.                         int new_dist = dfs(adj, visited, pr, dist+1);
  38.                         max_dist = max(max_dist, new_dist);
  39.                         //DEBUG("current dist: " << dist);
  40.                 }
  41.         }
  42.         visited[i][j] = max_dist;
  43.         return max_dist;
  44. }
  45.  
  46. int solve() {
  47.         vector<vector<char>> adj (h, vector<char>(w));
  48.         vector<vector<int>> dp (h, vector<int>(w, -1));
  49.         //vector<vector<bool>> visited (h, vector<bool>(w));
  50.         vector<pair<int, int>> start_pos;
  51.         int d = 0, d_max = 0;
  52.         char t;
  53.  
  54.         for(int i = 0; i < h; i++) {
  55.                 for(int j = 0; j < w; j++) {
  56.                         cin >> t;
  57.                         adj[i][j] = t;
  58.                         if(t == 'A') start_pos.push_back(make_pair(i, j));
  59.                 }
  60.         }
  61.  
  62.         // reuse visited array
  63.         for(const auto& pos: start_pos) {
  64.                 d = dfs(adj, dp, pos, d);
  65.                 d_max = max(d, d_max);
  66.                 d = 0;
  67.         }
  68.  
  69.         if(start_pos.size())
  70.                 return d_max+1;  // include source
  71.         else
  72.                 return 0;
  73. }
  74.  
  75. int main() {
  76.         ios_base::sync_with_stdio(false);
  77.         cin.tie(NULL);
  78.  
  79.         int num = 1;
  80.         cin >> h >> w;
  81.         do {
  82.                 int result = solve();
  83.                 cout << "Case " << num << ": " << result << "\n";
  84.                 num++;
  85.                 cin >> h >> w;
  86.         } while(!(h == 0 && w == 0));
  87.  
  88.         return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1: 0
https://ideone.com/IiPff9
problem ABCPATH, based on SPOJ submission 35845065 (CPP14), 2026-07-06 20:15:02
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!