Artifact 5b09cb848fba39308e5160aa3565b9a0ee09ebcc

• File SRM/398/1B.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <vector>
#include <map>
#include <cstring>
using namespace std;


long long dp[51][51][51][51]; // y,x,n,i

struct CountPaths
{
	vector <int> difPaths(int r, int c, vector <int> fieldrow, vector <int> fieldcol)
	{
		int k = fieldrow.size();
		map< pair<int,int>, int > f;
		for(int i=0; i<fieldrow.size(); ++i)
			f[make_pair(fieldrow[i],fieldcol[i])] = i;

		memset(dp, 0, sizeof(dp));
		if( f.count( make_pair(1,1) ) )
			dp[1][1][1][ f[make_pair(1,1)]+1 ] = 1;
		else
			dp[1][1][0][0] = 1;

		for(int y=1; y<=r; ++y)
		for(int x=(y==1?2:1); x<=c; ++x)
		{
			if( f.count(make_pair(y,x)) ) {
				int I = f[make_pair(y,x)];
				for(int n=1; n<=k; ++n) {
					int sum = 0;
					for(int i=0; i<=I; ++i) {
						if( y>=2 )
							sum += dp[y-1][x][n-1][i];
						if( x>=2 )
							sum += dp[y][x-1][n-1][i];
					}
					dp[y][x][n][I+1] = sum % 1000007;
				}
			} else {
				for(int n=0; n<=k; ++n) {
					for(int i=0; i<=k; ++i) {
						int sum = 0;
						if( y>=2 )
							sum += dp[y-1][x][n][i];
						if( x>=2 )
							sum += dp[y][x-1][n][i];
						dp[y][x][n][i] = sum % 1000007;
					}
				}
			}
		}

		vector<int> ans;
		for(int n=0; n<=k; ++n) {
			int sum = 0;
			for(int i=0; i<=k; ++i)
				sum += dp[r][c][n][i];
			ans.push_back( sum % 1000007 );
		}
		return ans;
	}
};