Algorithm
problem link- https://www.spoj.com/problems/ABCPATH/
ABCPATH - ABC Path
You will be given a 2-dimensional grid of letters. Find the length of the longest path of consecutive letters, starting at 'A'. Paths can step from one letter in the grid to any adjacent letter (horizontally, vertically, or diagonally).
For example, in the following grid, there are several paths from 'A' to 'D', but none from 'A' to 'E':
One such path is:
Input
Each test case will start with a line contains two integers H, W the height and width of the grid respectively 1 <= H, W <= 50. Then H lines follow each of W uppercase letters only. Input terminates with H = 0 and W = 0.
Output
For each test case print “Case C: X” without quotes where C is the case number starting with 1 and X is the solution.
Example
Sample Input: 4 3 ABE CFG BDH ABC 0 0 Sample Output: Case 1: 4
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
/*My First Template :D*/
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a) printf("%d\n", a)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b) si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
char matrix[55][55];
int visited[55][55];
int n, m;
int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};
bool isValid(int x, int y){
if(x >= 0 && x < n && y >= 0 && y < m)
return true;
return false;
}
int maxx = 0;
void dfs(int x, int y, char current){
// cout<<current<<endl;
visited[x][y] = 1;
char next = current+1;
maxx = max(maxx, current-'A'+1);
if(current == 'Z')
return;
for(int i = 0;i < 8; i++){
int tempX = x+dx[i];
int tempY = y+dy[i];
if(isValid(tempX, tempY) && !visited[tempX][tempY] && matrix[tempX][tempY] == next){
dfs(tempX, tempY, next);
}
}
}
int main(){
io;
int kase = 1;
while(1){
cin>>n>>m;
if(n == 0 && m == 0)
break;
for(int i = 0;i < n; i++){
for(int j = 0;j < m; j++){
cin>>matrix[i][j];
}
}
maxx = 0;
for(int i = 0;i < n; i++){
for(int j = 0;j < m; j++){
if(matrix[i][j] == 'A'){
memset(visited, 0, sizeof(visited));
dfs(i,j, 'A');
}
}
}
cout<<"Case "<<kase<<": ";
cout<<maxx<<endl;
kase++;
}
return 0;
}Input
4 3
ABE
CFG
BDH
ABC
0 0
ABE
CFG
BDH
ABC
0 0
Output
Case 1: 4
#2 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
class ABCPATH {
public static void main(String[] args)throws Exception{
Parser in = new Parser(System.in);
StringBuilder string = new StringBuilder();
int rows = in.nextInt();
int cols = in.nextInt();
int count = 1;
while(rows != 0 && cols != 0){
char[][] grid = new char[rows+2][cols+2];
boolean[][] visited = new boolean[rows+2][cols+2];
Queue<Letter> q = new LinkedList<Letter>();
for(int i = 0; i < cols+2; i++){
grid[0][i] = '#';
grid[rows+1][i] = '#';
}
for(int j = 1; j < rows+1; j++){
grid[j][0] = '#';
String line = in.next();
for(int k = 0; k < line.length(); k++){
grid[j][k+1] = line.charAt(k);
if(grid[j][k+1] == 'A'){
q.add(new Letter(j, k+1, 1, 0));
visited[j][k+1] = true;
}
}
grid[j][cols+1] = '#';
}
int[] xValues = {0,1,-1,0,1,1,-1,-1};
int[] yValues = {1,0,0,-1,1,-1,1,-1};
Letter current = null;
while(!q.isEmpty()){
current = q.remove();
for(int m = 0; m < 8; m++){
int x = xValues[m] + current.x;
int y = yValues[m] + current.y;
if(grid[x][y]-'A' == current.charValue+1 && !visited[x][y]){
visited[x][y] = true;
q.add(new Letter(x,y,current.dist+1, grid[x][y]-'A'));
}
}
}
if(current == null){
string.append("Case " + count + ": 0\n");
}else{
string.append("Case " + count + ": " + current.dist + "\n");
}
rows = in.nextInt();
cols = in.nextInt();
count++;
}
System.out.print(string);
}
}
class Letter{
int x,y,dist,charValue;
public Letter(int x, int y, int dist, int charValue){
this.x = x;
this.y = y;
this.dist = dist;
this.charValue = charValue;
}
}
class Parser
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Parser(InputStream in)
{
din = new DataInputStream(in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public long nextLong() throws Exception
{
long ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = c == '-';
if (neg) c = read();
do
{
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg) return -ret;
return ret;
}
//reads in the next string
public String next() throws Exception
{
StringBuilder ret = new StringBuilder();
byte c = read();
while (c <= ' ') c = read();
do
{
ret = ret.append((char)c);
c = read();
} while (c > ' ');
return ret.toString();
}
public int nextInt() throws Exception
{
int ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = c == '-';
if (neg) c = read();
do
{
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg) return -ret;
return ret;
}
private void fillBuffer() throws Exception
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1) buffer[0] = -1;
}
private byte read() throws Exception
{
if (bufferPointer == bytesRead) fillBuffer();
return buffer[bufferPointer++];
}
}Input
4 3
ABE
CFG
BDH
ABC
0 0
ABE
CFG
BDH
ABC
0 0
Output
Case 1: 4
Demonstration
SPOJ Solution-ABC Path-Solution in C, C++, Java, Python