【洛谷P 1022】川を渡る卒
5034 ワード
川を渡る
構想は、繰返し式を用いてパスバー数を算出し、配列に記録する である.
コード#コード#
構想
コード#コード#
#include
#include
using namespace std;
#define LOCAL 1
/*
1. -1
2. 0
3. 0
4.
*/
// 0, , long long
long long m[21][21];
int main(){
//
#if LOCAL
freopen ("datain.txt","r",stdin);
freopen ("dataout.txt","w",stdout);
#endif
// 8
int no[8][2] = { {1,2},{-1,2},{1,-2},{-1,-2},
{2,1},{-2,1},{2,-1},{-2,-1}
};
// ,
int bx,by,mx,my;
cin >> bx >> by >> mx >> my;
// -1
m[mx][my] = -1;
for(int i = 0; i < 8; i++){
int t1 = no[i][0] + mx;
int t2 = no[i][1] + my;
//
if(0 <= t1 && t1 <= bx && 0 <= t2 && t2 <= by){
m[t1][t2] = -1;
}
}
//
m[0][0] = 1;
for(int i = 0; i <= bx; i++){
for(int j = 0; j <= by; j++){
// ,
if(m[i][j] == -1){
continue;
}
//
if(i - 1 >= 0 && m[i-1][j] != -1){
m[i][j] += m[i-1][j];
}
//
if(j - 1 >= 0 && m[i][j-1] != -1){
m[i][j] += m[i][j-1];
}
}
}
//
// for(int i = 0; i <= bx; i++){
// for(int j = 0; j <= by; j++){
// cout << m[i][j] << "\t";
// }
// cout << endl;
// }
cout << m[bx][by] << endl;
return 0;
}