Problem in array dfs question

[aryan_0406]

Hello friends,
I was solving an array problem on leetcode using DFS but even after checking out my solution many times I am not able to find out what’s the problem with my solution.

Question- https://leetcode.com/problems/word-search/
Solution link- https://ideone.com/foZ4sv

I would be very thankful if someone helps me with this.

[simes]

Are you going to fix the compilation errors in the ideone link?

[aryan_0406]

hi @simes I have removed all the compilation errors.
I have also find out the input for which answer is coming wrong which is mentioned in the ideone code.

I think the inrange function is causing some undefined behaviour but I am not able to find that.

Plz help.

[simes]

#define inrange(i,j,n,m) (i>=0 && i<n && j>=0 && j<m)?true:false

What’s wrong with this? Remember it’s a macro, not a function call.

[aryan_0406]

okay fine, but still did you find any problem with the code?

if(inrange(i+1,j,n,m) && board[i+1][j]==word[ind] && !visited[i+1][j])

When I was debugging I found that even for two different letters of board[i+1][j] and word[ind] the statements within the above written if conditional were getting executed.

[simes]

Yes, the macro is wrong.

[aryan_0406]

But why I can’t use a macro like this.
Where can I find some good explanation on that?

[simes]

A macro is simply a parameterised substitution. So this

if(inrange(i+1,j,n,m) && board[i+1][j]==word[ind] && !visited[i+1][j])

becomes this

if((i+1>=0 && i+1<n && j>=0 && j<m)?true:false && board[i+1][j]==word[ind] && !visited[i+1][j])

Is the problem more obvious now?

[aryan_0406]

if((i+1>=0 && i+1<n && j>=0 && j<m)?true:false && board[i+1][j]==word[ind] && !visited[i+1][j])

But what’s wrong with this if i and j have proper constraints then (i+1>=0 && i+1<n && j>=0 && j<m)?true:false will return true and then board[i+1][j]==word[ind] will be evaluated which will give false if letters are different and overall -> true and false will give false.
But still if statement is getting evaluated.

Am I interpreting it the wrong way?

[simes]

I think it’s being interpreted like this:

if((i+1>=0 && i+1<n && j>=0 && j<m) ? (true) : (false && board[i+1][j]==word[ind] && !visited[i+1][j])))

so all it’s really checking is the array bounds, and not the word matches or visited. Which matches up with what I saw when testing it.

Test it. Replace

#define inrange(i,j,n,m) (i>=0 && i<n && j>=0 && j<m)?true:false

with

#define inrange(i,j,n,m) (i>=0 && i<n && j>=0 && j<m)

[aryan_0406]

I got it @simes.
Thanks for your help