# 2527. Fj & haozi

int main()

### {

int w;
cin>>w;
while(w--){
int n,p,m,t,dp[102][102]={0};
cin>>n>>p>>m>>t;
dp[p][0]=1;
dp[p][1]=0;
dp[p][2]=2;
int i,j;
for(j=1;j<=m;j++){//分钟
for(i=1;i<=n;i++){//在哪一栋
if(i<n){
dp[i][j]=dp[i-1][j-1]+dp[i+1][j-1];
}
else{
dp[i][j]=dp[i-1][j-1];
}
}
}
cout<<dp[t][m]<<endl;
}


### }

//n:总共楼层数,p起点，m时间，t终点
#include <bits/stdc++.h>
using namespace std;
int n,p,m,t;
int ans = 0;        //方案数

void dfs(int ind,int time) {
if(ind > n || time > m) return;
if(ind == t && time == m) ans++;        //到达终点

if(ind==n) dfs(ind-1,time+1);
else if(ind==1) dfs(ind+1,time+1);
else {
dfs(ind-1,time+1);
dfs(ind+1,time+1);
}
}

int main() {
int cas;cin>>cas;
while(cas--) {
ans = 0;
cin>>n>>p>>m>>t;
dfs(p,0);
cout<<ans<<endl;
}
return 0;
}

//dp[i][j]表示第i分钟到第j栋房子的方案
#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 101;
int dp[maxn][maxn];
int n;
int m;
int _begin;
int _end;

int main() {
int num;
cin >> num;
for (int k = 0; k < num; ++k) {
memset(dp, 0, sizeof(dp));
cin >> n >> _begin >> m >> _end;
dp[0][_begin] = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (j < n) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
}
else {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
cout << dp[m][_end] << endl;
}
return 0;
}


DFS

#include <iostream>
using namespace std;

int n;
int m;
int _begin;
int _end;
int ans;

void DFS(int index, int count) {
if (count == m) {
if (index == _end) {
ans++;
}
return;
}
if (index < n) {
DFS(index + 1, count + 1);
}
if (index > 1) {
DFS(index - 1, count + 1);
}
}

int main() {
int num;
cin >> num;
for (int i = 0; i < num; ++i) {
cin >> n >> _begin >> m >> _end;
ans = 0;
DFS(_begin, 0);
cout << ans << endl;
}
return 0;
}


#include <iostream>
using namespace std;
int main()
{
int cas,n,p,m,t;
cin>>cas;
for (;cas>0;--cas)
{
cin>>n>>p>>m>>t;
int d[102][102]={0};
int i,j;
d[p][0]=1;
for (j=1;j<m+1;++j)
for (i=1;i<n+1;++i)
d[i][j]=d[i-1][j-1]+d[i+1][j-1];
cout<<d[t][m]<<endl;
}
}


int level(int p, int m){
if (m <= 0){
if (p == t)
count++;
return 0;
}
if (p == 1) level(2, m - 1);
else{
if (p == n) level(n - 1, m - 1);
else{
level(p + 1, m - 1);
level(p - 1, m - 1);
}
}
}