I am getting WA for problem CIJEVI. Here is brief logic what I am doing-
I have taken input in array arr
and stored the indices of M and Z. If any of them have one pipe adjacent to it I run dfs from that cell(one adjacent to M or Z having a pipe). In function dfs I check which type of pipe the cell has and then proceed to function process with appropriate arguments depending upon the pipe type. In function process , I check for the adjacent locations of the cell and if it does not have a '.' , I call dfs with that new cell. If during dfs I reach a point such that there is no way forward, I call function newadd. In newadd I find the appropriate pipe missing. Here is my code-
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair <int , int > pii;
typedef pair <ll , ll > pll;
typedef pair <pii,int > ppi;
typedef pair <int ,pii> piii;
typedef pair <char,char> pcc;
typedef vector <int > vi;
typedef vector <ll > vl;
typedef vector <char> vc;
typedef vector <vc> vcc;
typedef vector <string> vs;
typedef vector <vi> vii;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
#define all(c) c.begin() , c.end()
#define INF (1000000000)
#define ull unsigned long long
#define s(n) scanf("%d",&n)
#define s2(a,b) scanf("%d %d",&a,&b)
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
# define PI 3.14159265358979323846
#define pb push_back
//#define for(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
ll gcd(ll a,ll b) {while(b) {ll temp=a; a=b; b=temp%b; } return a; }
ll lcm(ll a,ll b) {return (a/gcd(a,b))*b; }
string NumberToString ( ll Number ){ stringstream ss; ss << Number; return ss.str();}
int isPrime(ll n){ if (n==2) return 1; if (n%2==0) return 0; for (ll i=3;i<=sqrt(n);i+=2) if (n%i==0) return 0; return 1;}
int ans=0,R,C;
int inRange(int a,int b){if(a>=0 && a < R && b>=0 && b< C) return 1; return 0;}
char arr[26][26];
map < char, vi > M2;
//vi dr1(1,0);
//M2['1']=vector <int> (1,0);
int dr1[]={1,0};//down,right
int dc1[]={0,1};
int dr2[]={-1,0};//up,right
int dc2[]={0,1};
int dr3[]={-1,0};//left,up
int dc3[]={0,-1};
int dr4[]={1,0};//left,down
int dc4[]={0,-1};
int dr5[]={-1,1};//down,up
int dc5[]={0,0};
int dr6[]={0,0};//left,right
int dc6[]={-1,1};
int dr7[]={0,0,-1,1}; //left,right ,top ,down
int dc7[]={-1,1,0,0};
void process(int r,int c,int dr[] , int dc[]);
char left1[]={'1','2','+','-','M','Z'};
char right1[]={'3','4','+','-','M','Z'};
char up1[]={'1','4','+','|','M','Z'};
char down1[]={'2','3','+','|','M','Z'};
map <int,pii> M1;
int vis[26][26];
void dfs(int r,int c)
{
vis[r][c]=1;
if(arr[r][c]=='1')
process(r,c,dr1,dc1);
if(arr[r][c]=='2')
process(r,c,dr2,dc2);
if(arr[r][c]=='3')
process(r,c,dr3,dc3);
if(arr[r][c]=='4')
process(r,c,dr4,dc4);
if(arr[r][c]=='|')
process(r,c,dr5,dc5);
if(arr[r][c]=='-')
process(r,c,dr6,dc6);
if(arr[r][c]=='+')
process(r,c,dr7,dc7);
}
int check(int r,int c,char dr[])
{
for(int i=0;i<6;i++)
{
if(arr[r][c]==dr[i])
return 1;
}
return 0;
}
void newadd(int r,int c)
{
int x0=r+dr7[0],y0=c+dc7[0],x1=r+dr7[1],y1=c+dc7[1],x2=r+dr7[2],y2=c+dc7[2],x3=r+dr7[3],y3=c+dc7[3];
int leftt=0,rightt=0,upp=0,downn=0;
if(inRange(x0,y0) && check(x0,y0,left1))
leftt=1;
if(inRange(x1,y1) && check(x1,y1,right1))
rightt=1;
if(inRange(x2,y2) && check(x2,y2,up1))
upp=1;
if(inRange(x3,y3) && check(x3,y3,down1))
downn=1;
if(leftt | rightt | upp | downn)
cout << r+1 << " " << c+1 ;
else
return;
//cout << leftt << " " << rightt << " " << upp << " " << downn << endl;
if(leftt && rightt && upp && downn)
cout << " +" << endl;
else if(rightt && downn && !leftt && !upp)
cout << " 1" << endl;
else if(rightt && upp && !leftt && !downn)
cout << " 2" << endl;
else if(leftt && upp && !downn && !rightt)
cout << " 3" << endl;
else if(leftt && downn && !rightt && !upp)
cout << " 4" << endl;
else if(upp && downn && !leftt && !rightt)
cout << " |" << endl;
else if(rightt && leftt && !downn && !upp)
cout << " -" << endl;
else
cout << " NO" << endl;
}
void process(int r,int c,int dr[] , int dc[])
{
//cout << r << " " << c << endl;
for(int i=0;i<sizeof(dr)/sizeof(*dr);i++)
{
int x=r+dr[i],y=c+dc[i];
//cout << "X and Y are = " << x << " " << y << endl;
if(inRange(x,y) && !vis[x][y] && arr[x][y]!='.')
dfs(x,y);
if(inRange(x,y) && !vis[x][y] && arr[x][y]=='.')
{
newadd(x,y);
break;
}
}
}
int main()
{
cin >> R >> C;
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
cin >> arr[i][j];
if(arr[i][j]=='M')
M1[0]=pii(i,j);
if(arr[i][j]=='Z')
M1[1]=pii(i,j);
}
}
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
vis[i][j]=0;
//cout << endl;
}
int a=M1[0].first,b=M1[0].second;
int a1=-1,b1=-1,a2=-1,b2=-1;
for(int i=0;i<4;i++)
{
int x=a+dr7[i],y=b+dc7[i];
if(inRange(x,y) && arr[x][y]!='.')
{ a1=x,b1=y;break;}
}
//cout << a1 << " " << b1 << endl;
int a22=M1[1].first,b22=M1[1].second;
for(int i=0;i<4;i++)
{
int x=a22+dr7[i],y=b22+dc7[i];
if(inRange(x,y) && arr[x][y]!='.')
{ a2=x,b2=y;break;}
}
if(a1!=-1 )
dfs(a1,b1);
if(a1==-1 && a2!=-1)
dfs(a2,b2);
if(R==1 && C==3)
cout << "1 2 -" << endl;
if(R==3 && C==1)
cout << "2 1 |" << endl;
//cout << sizeof(dr7)/sizeof(*dr7) << endl;
//dfs(a,b);
return 0;
}
I have checked many test cases, all of them giving correct answer. Still I get WA on the judge. Can someone please point out my mistake or any special case which my code seems to miss out. Thanks in advance.Also , point out if I violate any rules of the forum as this is my first post and I dont understand all the rules here yet.