as title of question suggests have find number of occurences of particular string in grid of characters of size n(<=1000). can go diagonally. example
5 //n b x x x //grid x x x x x b b x x x x x x x b x x aba //finding occurence in above grid answer 14 i don't know how solve question. have seen people doing kind of recursion (they it's backtracking).
what have done till now
i tried solve using bfs , gives right answer small cases not giving large n.
my code bfs have tried
#include <bits/stdc++.h> using namespace std; #define pb push_back #define nline puts("\n") vector<pair<int,int> >v; #define e .00000001 string s; char ch[1000][1000]; int dx[4] = {1, 1, -1, -1}; int dy[4] = { -1, 1, 1, -1 }; char vis[1000][1000]; int n,total=0; struct data { int x,y; void set(int _x,int _y) { x=_x; y=_y; } }; void bfs(data src) { vis[src.x][src.y]=true; queue<data>q; q.push(src); int len=1; while(not q.empty()) { data ss=q.front(); q.pop(); for(int i=0;i<4;i++) { int xx=dx[i]+ss.x; int yy=dy[i]+ss.y; if(len<=s.length()-1 , ch[xx][yy]==s[len] , xx>=0 , xx<n , yy>=0 , yy<n , (not vis[xx][yy])) { vis[xx][yy]=true; data tem; tem.set(xx,yy); q.push(tem); len++; } } } if(len==s.length())total++; } int main() { cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>ch[i][j]; cin>>s; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(ch[i][j]==s[0]) { data start; start.set(i,j); bfs(start); memset(vis,0,sizeof vis); } } } cout<<total<<endl; return 0; } can me out? :)
a recursive solution, not asked hope helps.
we'll use function check how many occurrences there every element of matrix. if grid[1][1] matches first character of string need check if diagonal neighboring elements match second character of string. remove first character of string , call same function on neighboring elements new string.
(python code should understandable-ish if don't know python)
first create helper function return valid diagonal neighbors.
def valid_neighbors(i,j, n): # returns list of valid diagonal neighbors(do not exceed matrix borders). neighbors = [(i-1, j-1), (i+1, j+1), (i+1, j-1), (i-1, j+1)] return [m m in neighbors if (0 <= m[0] < n) , (0 <= m[1] < n)] next recursive function checks occurrences (comments explain logic).
def find(matrix, n, i, j, string): occurrences = 0 if string == matrix[i][j]: # found 1 occurrence, nothing else do. return 1 if string[0] == matrix[i][j]: # first letter of string match, seek possible occurrences. new_i, new_j in valid_neighbors(i, j, n): # go on valid diagonal moves if matrix[new_i][new_j] == string[1]: # if char in new location match next character of string, # recursively call function new position , input string # minus first character ("abcd" -> "bcd"). occurrences += find(matrix, n, new_i, new_j, string[1:]) # return number of occurrences found. return occurrences that works on single element of matrix, need call function every element , sum results.
def wrapper(matrix, string): # call find on every element of matrix , sum results. occurrences = 0 n = len(matrix) in range(n): j in range(n): occurrences += find(matrix, n, i, j, string) return occurrences you build caching mechanism improve performance.
running code on input matrix:
mat = [ ['b', 'x', 'a', 'x', 'x'], ['x', 'a', 'x', 'x', 'x'], ['x', 'b', 'b', 'x', 'x'], ['x', 'a', 'x', 'a', 'x'], ['x', 'x', 'b', 'x', 'x'] ] print wrapper(mat, "aba") 14 
Comments
Post a Comment