PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Naman Chaurasia
DIFFICULTY: EASY-MEDIUM
PREREQUISITES:
Math
PROBLEM:
given a 2D grid of characters. The characters in the grid can be read from top to down, down to top, left to right, right to left and diagonally(diagonally in all 4 directions NW to SE, SE to NW, NE to SW and SW to NE).
find the number of names found in the grid from given set of names.
QUICK EXPLANATION:
Basically for each name in list L, find a way to check in all 8 directions given, if set of characters are there matching the name.
EXPLANATION:
convert the given grid into a single string combining strings from all 8 directions
eg-: for grid
[a b]
[c d]
strings formed from
- top to down: ac, bd
2.down to top: ca,db
3.left to right: ab,cd
4.right to left: ba,dc
5.NW to SE: c,ad,b
6.SE to NW: c,da,b
7.NE to SW: a,bc,d
8.SW to NE: a,cb,d
Note-: separate each string obtained by a special character.
let this combined string be called STR.
and now just compare if a substring exists in this STR matching the name
calculating time complexity- O(10^5)
grid contains maximum 100 characters
8 possible directions N,S,E,W,NW to SE, SE to NW, NE to SW and SW to NE
length of combined string =8*100 (10^3)
10 strings of 10 characters= 100(10^2)
SOLUTIONS:
Setter's Solution
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int n=int.Parse(Console.ReadLine());
string[]ss=Console.ReadLine().Split();
string[]vv=Console.ReadLine().Split();
int a=int.Parse(vv[0]);
int b=int.Parse(vv[1]);
string[] kk=new string[a];
for(int i=0;i<a;i++)
{
kk[i]=Console.ReadLine();
}
int count=0;
for(int i=0;i<n;i++)
{
if(yes(ss[i],kk)){count++;}
}
Console.WriteLine(count);
}
public static string san(string v,int t)
{
if(v.Length<=t)return v;
return v.Substring(v.Length-t);
}
public static bool yes(string s,string[]k)
{
for(int i=0;i<k.Length;i++)
{
string v="";
for(int j=0;j<k[0].Length;j++)
{
if(k[0].Length-j<s.Length)break;
v=k[i].Substring(j,s.Length);
if(v==s)return true;
if(ret(v)==s)return true;
}
}
for(int i=0;i<k[0].Length;i++)
{
string v="";
for(int j=0;j<k.Length;j++)
{
v+=k[j][i];
if(san(v,s.Length)==s)return true;
if(ret(san(v,s.Length))==s)return true;
}
}
for(int i=0;i<k.Length;i++)
{
for(int j=0;j<k[0].Length;j++)
{
string v="";
for(int t=j,u=i;t<k[0].Length && u>=0;t++,u--)
{
v+=k[u][t];
if(v.Length==s.Length)break;
}
if(v==s)return true;
if(ret(v)==s)return true;
}
}
for(int i=0;i<k.Length;i++)
{
for(int j=0;j<k[0].Length;j++)
{
string v="";
for(int t=j,u=i;t<k[0].Length && u<k.Length;t++,u++)
{
v+=k[u][t];
if(v.Length==s.Length)break;
}
if(v==s)return true;
if(ret(v)==s)return true;
}
}return false;
}
public static string ret(string s)
{
char[]cc=s.ToCharArray();
Array.Reverse(cc);
return new string(cc);
}
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
ll n,i,j,k,r,c,x,ans=0;
cin>>n;
string s[n],com="";
for(i=0;i<n;i++)cin>>s[i];
cin>>r>>c;
string grid[r];
for(i=0;i<r;i++)cin>>grid[i];
//left to right
for(i=0;i<r;i++,com+=".")
for(j=0;j<c;j++)
com+=grid[i][j];
//right to left
for(i=0;i<r;i++,com+=".")
for(j=c-1;j>=0;j--)
com+=grid[i][j];
//down to up
for(j=0;j<c;j++,com+=".")
for(i=r-1;i>=0;i--)
com+=grid[i][j];
//up to down
for(j=0;j<c;j++,com+=".")
for(i=0;i<r;i++)
com+=grid[i][j];
//south west
for(int j=0;j<=r-1+c-1;j++,com+=".")
for(int i=0;i<r;i++)
if(0<=j-i&&j-i<c)
com+=grid[i][j-i];
//north east
for(int j=0;j<=r-1+c-1;j++,com+=".")
for(int i=r-1;i>=0;i--)
if(0<=j-i&&j-i<c)
com+=grid[i][j-i];
//south east
for(int j=-(c+r);j<=c+r;j++,com+=".")
for(int i=0;i<r;i++)
if(0<=i+j&&i+j<c)
com+=grid[i][i+j];
//north west
for(int j=-(c+r);j<=c+r;j++,com+=".")
for(int i=r-1;i>=0;i--)
if(0<=i+j&&i+j<c)
com+=grid[i][i+j];
//cout<<com<<"\n";
for(int i=0;i<n;i++)
for(int j=0;j+s[i].size()-1<com.size();j++)
if(com.substr(j,s[i].size())==s[i])
{
ans++;
break;
}
cout<<ans<<endl;
return 0;
}