# Fill The Matrix Bfs Approach

i have applied bfs in my code i am traversing level order and assigning value to node and then if i found anything contradicting then answer that no.please help with my solution https://www.codechef.com/viewsolution/15369875

This is what I was doing at first!!

You missed a vital point while assigning the values to the nodes.

The problem statement states that: A matrix `B` (consisting of integers) of dimension `N × N` is said to be good if there exists an array `A` (consisting of integers) such that `B[i][j] = |A[i] - A[j]|`, where `|x|` denotes absolute value of integer `x`.

Consider one of the `m` queries to be: 1 2 1

What your code does is initialize `node 1` with 1 and `node 2` with “value of node 1 + 1”.

So, `val[1]` contains 1 and `val[2]` contains 2. Is this correct?

No, its partially correct!

If you assign `val[1]` with 1, then `val[2]` can be both 2 as well as 0 ( the problem statement clearly mentions integers).

If `val[2] = 0`, then `|val[1] - val[2]| = 1`.

If `val[2] = 2`, then `|val[1] - val[2]| = 1`.

You filled a single slot in the value array(val[]) in just one way while there were two possible ways to fill a single slot in val[]. This mistake compounded as the number of queries increased.

How to get AC then??

There’s just a bit of change that needs to be done with your code.

You fill `val[]` the same as you are doing now. But instead of,

`````` if(abs(val[x]-val[v[x][y].first])!=v[x][y].second)
``````

do this,

`````` if(abs((val[x]-val[v[x][y].first])-v[x][y].second) % 2 != 0)
``````

Since, we can fill a single slot in two ways (but we are just doing it in one way), the difference should be either 0(this case arises if the test case was for a matrix which was filled as the way we are doing i.e. adding 1) or a multiple of 2 (this case arises if the test case was for matrix which has some of its cells filled in the other way i.e. subtracting 1).

Consider one of the `m` queries to be 2 2 1. Clearly, this is not possible. Your code misses a check for such cases. Add this too.