Sep 2019
1 / 4
Sep 2019
Jun 2021
abhinav_mani
Sep '19

ABCPATH problem10

I have been trying to solve problem ABCPATH but repeatedly getting WA. I havent been able to find out the bug in my code… help would be really appreciated.
here is my code
thanks in advance smile

import java.util.;
import java.lang.;

class Main
{
static boolean vis[][];
static int dfs(char ch,char a[][],int i,int j)
{
vis[i][j]=true;
int max=0;
for(int k=-1;k<=1;k++)
{
for(int l=-1;l<=1;l++)
{
if(!vis[i+k][j+l])
{
if(ch+1==a[i+k][j+l])
{
int c=dfs((char)(ch+1),a,i+k,j+l);
if(c>max)
max=c;
}
}
}
}
return max+1;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
char a[][]=new char[52][52];
int h,w,C=1;
h=sc.nextInt();
w=sc.nextInt();
StringBuilder ans=new StringBuilder();
do
{
vis=new boolean[52][52];
int max=0;
for(int i=1;i<=h;i++)
{
String s=sc.next();
for(int j=1;j<=w;j++)
{
a[i][j]=s.charAt(j-1);
}
}
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
if(a[i][j]==‘A’)
{
int val=dfs(‘A’,a,i,j);
if(val>max)
{
max=val;
}
}
}
}
h=sc.nextInt();
w=sc.nextInt();
ans.append(“Case “).append(C++).append(”: “).append(max).append(”\n”);
}while(h!=0&&w!=0);
System.out.println(ans);
}

}

  • created

    Sep '19

  • last reply

    Jun '21
  • 3

    replies

  • 1.0k

    views

  • 3

    users

  • 1

    like

  • 2

    links

simes
Sep '19

Try this: Notice that the first and third cases are the same, so you’d expect them to give the same answer.

2 2
AA
AA
5 5
AAABB
BBBBB
CDCDC
DDDDD
EEEEE
2 2
AA
AA
0 0

1 year later
farzamkoohi
Jun '21

I have a problem in ABCPATH.
my code getting TLE and I confused.
this is my code.
please help

    #include <bits/stdc++.h>

using namespace std;

const int maxN = 3000;
int h, w;
char x;
int vers[maxN];
vector <int> edges[maxN];
vector <int> result;
int maximum = 0;
vector <int> now;
vector <int> zeroes;


void dfs(int ind)
{
    now.push_back(ind);
    for (int i = 0; i != edges[ind].size(); i++)
    {
        dfs(edges[ind][i]);
    }
    int f = now.size();
    maximum = max(maximum , f);
    now.pop_back();
}

int main()
{
    cin >> h >> w;
    while (h != 0 && w != 0)
    {
        maximum = 0;
        zeroes.clear();
        memset(edges , NULL , sizeof(edges));
        for (int i = 0; i != h*w; i++)
        {
            cin >> x;
            vers[i] = x - 'A';
            if (vers[i] == 0)
                zeroes.push_back(i);
        }
        for (int i = 0; i != h*w; i++)
        {
           if(((i/w - 1)*w) + i%w >= 0 && vers[i] + 1 == vers[((i/w - 1)*w) + i%w])
            edges[i].push_back(((i/w - 1)*w) + i%w);
           if (((i/w + 1) *w) + i%w <= h*w-1 && vers[i] + 1 == vers[((i/w + 1) *w) + i%w])
            edges[i].push_back(((i/w + 1) *w) + i%w);
           if ((i+1) / w == i/w && vers[i] + 1 == vers[i+1])
            edges[i].push_back(i+1);
           if ((i-1)/w == i/w && vers[i] + 1 == vers[i-1])
            edges[i].push_back(i-1);
           if ((i-w-1)/w == i/w -1 && i /w != 0 && i % w != 0 && vers[i] + 1 == vers[i-w-1])
            edges[i].push_back(i-w-1);
           if ((i-w+1)/w == i/w - 1 && i / w != 0 && i % w != w-1 && vers[i] +1  == vers[i-w+1])
            edges[i].push_back(i-w+1);
           if ((i+w-1)/w == i/w +1 && i /w != h-1 && i % w != 0 && vers[i] + 1 == vers[i+w-1])
            edges[i].push_back(i+w-1);
           if ((i+w+1)/w == i/w + 1 && i / w != h-1 && i % w != w-1 && vers[i] +1  == vers[i+w+1])
            edges[i].push_back(i+w+1);
        }
        for (int i = 0; i != zeroes.size(); i++)
            dfs(zeroes[i]);
        result.push_back(maximum);
        cin >> h >> w;
    }
    for (int i = 0; i != result.size(); i++)
        cout << "Case " << i+1 << ": " << result[i] << '\n';
}