## ABCPATH - ABC Path

no tags

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;
}``````
Copy The Code &

Input

cmd
4 3
ABE
CFG
BDH
ABC
0 0

Output

cmd
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;
}
}
}

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';
} 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);
} 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';
} 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++];
}
}``````
Copy The Code &

Input

cmd
4 3
ABE
CFG
BDH
ABC
0 0

Output

cmd
Case 1: 4