$3.$ Consider the unbounded version $($aka$.$ Infinitely large$)$ of the regular $2$D grid shown in the following Figure. The start state is at the origin, $(0,0),$ and the goal state is at $($x$,$ y$).$

a$.$ What is the branching factor b in this state space using breadth$-$first tree search? $($Hint: the tree search is not the same as the graph search, tree search don't $($no need to$)$ keep tracking whether it has been visited before or not. In graph search, you need track that. If it is already visited, it will be skipped and not put into the queue, therefore not expanded$)$

b$.$ How many distinct states are there at depth k $($for k $>0)?$

$-$ At depth k$,$ the number of distinct states would be b$^$k less the last goal. Therefore, we have $4^$k distinct states at depth k$.$

c$.$ What is the maximum number of nodes expanded by breadth$-$first tree search? $($Hint: you don't expand the last goal state when you reach that state, don't forgot $-1$ to the total number$)$