C++, BFS, 19ms


  • 0
    X

    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;
    
    }
    

Log in to reply
 

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