hdu 2125 Local area network

1570 ワード

1.テーマ
http://acm.hdu.edu.cn/showproblem.php?pid=2125
2.分析
2 D階段のような問題は、欠陥点の問題を処理する必要があるだけです.欠陥点の横縦座標の標識に注意し、当然の自分の感覚を考えてはいけない.動的計画で使用される決定:左と下の数値の和;
3.複雑度
空間複雑度O(MN);時間複雑度O(MN);
4.関連内容
アルゴリズムアルゴリズム:ダイナミックプランニングダイナミックプランニング
5.感想
2次元の階段の問題のように、いくつかの経典のテーマを繰り返して、自分の感覚を育成する必要があると感じています.
6.コード
#include <iostream>
using namespace std;
long f2125[40][40];
void init2125(int n,int m,int &x1,int &y1,int &x2,int &y2)
{
	int tempxy;
	if(x1==x2 && y1>y2) { tempxy=y1;	y1=y2;	y2=tempxy; }
	else if(y1==y2 && x1>x2) { tempxy=x1;	x1=x2;	x2=tempxy; }
	memset(f2125,0,sizeof(f2125));
	f2125[0][0]=1;
	for(int i=1;i<n;++i)// 
	{
		f2125[i][0]=f2125[i-1][0];
		if(i==x2 && y2==0 && i-1==x1 && y1==0) f2125[i][0]=0;
	}
	for(int j=1;j<m;++j)// 
	{
		f2125[0][j]=f2125[0][j-1];
		if(0==x2 && y2==j && j-1==y1 && x1==0) f2125[0][j]=0;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	int n,m,x1,y1,x2,y2;
	while(cin>>n>>m)
	{
		cin>>x1>>y1>>x2>>y2;
		init2125(n,m,y1,x1,y2,x2);
		for(int i=1;i<n;++i)// 
			for(int j=1;j<m;++j)// 
			{
				if(i==y2 && i-1==y1 && x1==j && x2==j) f2125[i][j]=f2125[i][j-1];
				else if(i==y2 && i==y1 && x1==j-1 && x2==j) f2125[i][j]=f2125[i-1][j];
				else f2125[i][j]=f2125[i-1][j]+f2125[i][j-1];
			}
		cout<<f2125[n-1][m-1]<<endl;
	}
	return 0;
}

7.参考文献