# C++, BFS, 19ms

• Use BFS to track next possible moves: The idea is for each (x,y), store how many ways to get here.

if (x,y) is a corner, total number increases by count * corner
if (x,y) is a boundary, total number increase by count * boundary
if (x,y) is interior, total number will not increase

``````int findPaths(int m, int n, int N, int i, int j) {
if (N == 0)
return 0;

long long total = 0;
int M = 1000000007;

queue<pair<int, int> > q;

q.push({ i * n + j, 1 });

int incr[5] = { 1, 0, -1, 0, 1 };

int corner = (m == 1 || n == 1) ? 3 : 2;
if (m == 1 && n == 1)
corner = 4;
int boundary = (m == 1 || n == 1) ? 2 : 1;
//for each (x,y) stores how many ways to get here.
while (!q.empty())
{
int num = q.size();
unordered_map<int, long long> nexts;
for (int k = 0; k < num; ++k)
{
int x = q.front().first / n;
int y = q.front().first % n;
long long count = q.front().second;

//if (x,y) is a corner, total number increase by  count * corner
//if (x,y) is a boundary, total number increase by  count * boundary
//if (x,y) is interior, totoal number will not increase
if (x == 0 && y == 0 || x == m - 1 && y == 0 || x == 0 && y == n - 1 || x == m - 1 && y == n - 1)
total += (long long)corner * count;
else if (x == 0 || y == 0 || x == m - 1 || y == n - 1)
total += (long long)boundary *count;

total = total % M;

q.pop();

//accumulate number of ways at same next_x, next_y
for (int i = 0; i < 4; ++i)
{
int next_x = x + incr[i];
int next_y = y + incr[i + 1];
if (next_x >= m || next_x < 0 || next_y >= n || next_y < 0)
continue;
nexts[next_x*n + next_y] += count;
}
}
--N;
if (N == 0)
break;

for (auto next : nexts)
q.push({ next.first, next.second % M });
}

return total%M;

}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.