# 294 条题解

• @ 2017-05-08 08:57:56
``````/*
递推即可
注意两个边界处理(即0行的递推和0列的递推)
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
int i,j,x,y,n,m,f[100][100];
long long ans[100][100];
scanf("%d%d%d%d",&n,&m,&x,&y);
memset(f,1,sizeof(f));
memset(ans,0,sizeof(ans));
ans[0][0]=1;
f[x][y]=0,f[x+1][y+2]=0,f[x-1][y+2]=0;
f[x+1][y-2]=0,f[x-1][y-2]=0,f[x+2][y+1]=0;
f[x-2][y+1]=0,f[x+2][y-1]=0,f[x-2][y-1]=0;
for (i=1; i<=n; i++)
if (f[i][0])
ans[i][0]=1;
else break;
for (i=1; i<=m; i++)
if (f[0][i])
ans[0][i]=1;
else break;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
if (f[i][j])
ans[i][j]=ans[i-1][j]+ans[i][j-1];
printf("%lld\n",ans[n][m]);
return 0;
}

``````
• @ 2022-08-10 15:43:20
``````#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
const ll N=50005;
ll i,j,m,n,x,y,b[25][25]={0};
ll c[9]={0,-2,2,-2,2,1,-1,-1,1},d[9]={0,1,-1,-1,1,-2,2,-2,2};
bool a[25][25]={0};
int main()
{
cin>>m>>n>>x>>y;
m+=2;n+=2;x+=2;y+=2;
a[x][y]=1;b[2][1]=1;
for(i=1;i<=8;i++)a[x+c[i]][y+d[i]]=1;
for(i=2;i<=m;i++)
{
for(j=2;j<=n;j++)
{
if(a[i][j]==1)
{
b[i][j]=0;
continue;
}
b[i][j]=b[i-1][j]+b[i][j-1];
}
}
cout<<b[m][n];
return 0;
}
``````
• @ 2017-11-24 20:07:21

//直接dfs

#include<iostream>
#include<cstdio>

using namespace std;

int a[20][20]={0};
int m,n,s,t,x,y;

void dfs(int aa,int bb)
{
if(aa==m&&bb==n){
t++;
return;
}
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
if(a[aa+i][bb+j]==0&&i+j==1&&aa+i<=m&&bb+j<=n)
dfs(aa+i,bb+j);
}
int main()
{
cin>>m>>n>>x>>y;
{if(x-2>=0&&y-1>=0) a[x-2][y-1] = 1;
if(x-2>=0&&y+1>=0) a[x-2][y+1] = 1;
if(x-1>=0&&y+2>=0) a[x-1][y+2] = 1;
if(x-2>=0&&y+1>=0) a[x-1][y-2] = 1;
if(x+1>=0&&y+2>=0) a[x+1][y+2] = 1;
if(x+2>=0&&y+1>=0) a[x+2][y+1] = 1;
if(x+2>=0&&y-1>=0) a[x+2][y-1] = 1;
if(x+1>=0&&y-2>=0) a[x+1][y-2] = 1;
}

a[x][y] = 1;
t = 0;
dfs(0,0);
cout<<t;
return 0;
}

• @ 2023-08-13 11:36:19
``````#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
long long c[22][22];
bool ok(int x,int y){
if((x==a)&&(y==b)){
return 1;
}
if((abs(x-a)==2)&&(abs(y-b)==1)){
return 1;
}
if((abs(x-a)==1)&&(abs(y-b)==2)){
return 1;
}
return 0;
}
long long dfs(int x,int y){
if((x>n)||(y>m)){
return 0;
}
if((x==n)&&(y==m)){
c[x][y]=1;
return 1;
}
if(c[x][y]!=-1){
return c[x][y];
}
if(ok(x,y)){
c[x][y]=0;
return 0;
}
c[x][y]=dfs(x+1,y)+dfs(x,y+1);
return c[x][y];
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
memset(c,-1,sizeof(c));
cin>>n>>m>>a>>b;
cout<<dfs(0,0)<<endl;
return 0;
}

``````
• @ 2023-08-13 11:35:06
``````#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
long long c[22][22];
bool ok(int x,int y){
if((x==a)&&(y==b)){
return 1;
}
if((abs(x-a)==2)&&(abs(y-b)==1)){
return 1;
}
if((abs(x-a)==1)&&(abs(y-b)==2)){
return 1;
}
return 0;
}
long long dfs(int x,int y){
if((x>n)||(y>m)){
return 0;
}
if((x==n)&&(y==m)){
c[x][y]=1;
return 1;
}
if(c[x][y]!=-1){
return c[x][y];
}
if(ok(x,y)){
c[x][y]=0;
return 0;
}
c[x][y]=dfs(x+1,y)+dfs(x,y+1);
return c[x][y];
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
memset(c,-1,sizeof(c));
cin>>n>>m>>a>>b;
cout<<dfs(0,0)<<endl;
return 0;
}

``````
• @ 2021-07-08 15:54:50

#include<iostream>
#include<cstring>
#include<cstdio>
#include<iomanip>
using namespace std;
long long a[30][30];
int g[30][30];
int u[8][2]={{2,1},{1,2},{2,-1},{1,-2},{-2,-1},{-1,-2},{-2,1},{-1,2}};
int main()
{
memset(g,0,sizeof(g));
int n,m,cx,cy,i,j,x,y;
scanf("%d%d",&m,&n);
scanf("%d%d",&x,&y);
g[x][y]=1;
a[x][y]=0;
for(i=0;i<=7;i++)
{
cx=x+u[i][0];
cy=y+u[i][1];
if(cx>=0&&cx<=m&&cy>=0&&cy<=n)
{
g[cx][cy]=1;
a[cx][cy]=0;
}
}
a[0][0]=0;
for(i=0;i<=m;i++)
{
if(g[i][0]==1)
{
while(i<=m)
{
a[i][0]=0;
i++;
}
}
else a[i][0]=1;
}
for(i=0;i<=n;i++)
{
if(g[0][i]==1)
{
while(i<=n)
{
a[0][i]=0;
i++;
}
}
else a[0][i]=1;
}

for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(g[i][j]==0)
a[i][j]=a[i-1][j]+a[i][j-1];
}
}
cout<<a[m][n];
return 0;
}

• @ 2021-06-28 08:02:50
``````#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 52;
const int dx[9] = {0, -2, -1, 1, 2, 2, 1, -1, -2}, dy[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
int n, m, l, r, p, t, k, ans, sum, tot, cnt, a[N], b[N], c[N], f[N][N], g[N][N];
{
register int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') f=-1;
ch = getchar();
}
while(isdigit(ch))
{
x=(x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
signed main()
{
f[1][1] = 1;
g[C][D] = 1;
for(int i = 1; i <= 8; i++)
{
g[C + dx[i]][D + dy[i]] = 1;
}
for(int i = 1; i <= A; i++)
{
for(int j = 1; j <= B; j++)
{
if(!g[i][j]) f[i][j] = max(f[i][j], f[i - 1][j] + f[i][j - 1]);
}
}
cout << f[A][B];
return 0;
}
``````
• @ 2020-04-08 23:56:37
``````#include <iostream>         //[2002普及组-D]过河卒
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 22;
typedef long long ll;
int n, m, X, Y;
ll dp[MAXN][MAXN];

void ini(int X, int Y)
{
int p[8][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
dp[X][Y] = 0;
int a, b;
for (int i = 0; i < 8; i++)
{
a = X + p[i][0];
b = Y + p[i][1];
if(a >= 0 && a <= n)
if(b >= 0 && b <= m)
dp[a][b] = 0;
}
}

int main()
{
cin >> n >> m >> X >> Y;
memset(dp, -1, sizeof(dp));
ini(X, Y);
for (int i = 1; i <= n; i++)
{
if(dp[i][0] == 0)
break;
dp[i][0] = 1;
}
for (int i = 1; i <= m; i++)
{
if(dp[0][i] == 0)
break;
dp[0][i] = 1;
}

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if(dp[i][j])
dp[i][j] = max((ll)0, dp[i - 1][j]) + max((ll)0,dp[i][j - 1]);

cout << dp[n][m] << endl;

return 0;
}

``````
• @ 2019-03-10 11:25:35
``````#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f;
int d[16][16],bx,by,hx,hy;
int t[2][9] = {{0,1,1,-1,-1,2,2,-2,-2},{0,2,-2,2,-2,1,-1,1,-1}};
int main(){
ios::sync_with_stdio(false);
cin>>bx>>by>>hx>>hy;
for(int i=0;i<9;i++){
int x=hx+t[0][i],y=hy+t[1][i];
if(x>=0&&x<=bx&&y>=0&&y<=by){
d[x][y] = -inf;
}
}
d[0][0] = 1;
for(int i=0;i<=bx;i++){
for(int j=0;j<=by;j++){
if(d[i][j]==-inf) continue;
if(i&&j) d[i][j]=d[i][j-1]+d[i-1][j];
if(i) d[i][j]=max(d[i][j],d[i-1][j]);
if(j) d[i][j]=max(d[i][j],d[i][j-1]);
}
}
cout<<d[bx][by];
return 0;
}

``````
• @ 2017-11-28 18:02:13
``````#include<stdio.h>
#include<math.h>
long long a[100][100]={{0}};
long long n,m,_n,_m;
int main() {
scanf("%lld%lld%lld%lld",&n, &m, &_n, &_m);
n++,m++,_n++,_m++;
a[0][1]=1;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if((fabs(i-_n)+fabs(j-_m)==3)&&(i!=_n)&&(j!=_m)||(i==_n&&j==_m))
continue;
else a[i][j]=a[i-1][j]+a[i][j-1];
printf("%lld", a[n][m]);
return 0;
}

``````
• @ 2017-11-21 20:38:25
``````#include <iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<vector>
#include<cstring>
#include<algorithm>
#define mod 7654321
#define FOR(i,x,y) for(i=x;i<=y;++i)
#define maxa 10000+100
using namespace std;
int n,m,p,q,ans = 0;
struct node
{
int x,y;
};
vector<node >v;
bool check(int x,int y)
{
int i,j;
if(x==p&&y==q)
return false;
FOR(i,-1,1)
for(j=-2;j<=2;j+=4)
if(i!=0)
{
int np =p+i;
int nq = q+j;
if(x==np&&y==nq)
return false;
}
FOR(i,-1,1)
for(j=-2;j<=2;j+=4)
if(i!=0)
{
int np =p+j;
int nq = q+i;
if(x==np&&y==nq)
return false;
}
return true;
}
bool check1(int x,int y)
{
int i;
FOR(i,0,v.size()-1)
if(x==v[i].x&&y==v[i].y)
return false;
return true;
}
void dfs(int x,int y)
{
// cout<<x<<" "<<y<<endl;
if(x>n)
return ;
if(y>m)
return ;
if(x==n&&y==m)
{
ans++;
return ;
}
else
{
if(check1(x,y+1))
dfs(x,y+1);
if(check1(x+1,y))
dfs(x+1,y);
}
}
int main()
{
cin>>n>>m>>p>>q;
int np,nq;
v.push_back(node{p,q});
int i,j;
FOR(i,-1,1)
for(j=-2;j<=2;j+=4)
if(i!=0)
{
int np =p+i;
int nq = q+j;
v.push_back(node{np,nq});
np = p+j;
nq =  q+i;
v.push_back(node{np,nq});
}
/* FOR(i,0,v.size()-1)
cout<<v[i].x<<" "<<v[i].y<<endl;*/
dfs(0,0);
cout<<ans<<endl;
}

``````
• @ 2017-10-24 23:11:01

被H2O坑了两次

``````#include<iostream>

using namespace std;

const int maxn=1010;
int dp[maxn][maxn]={0},map[maxn][maxn]={0};
int n,m,x,y;

int main()
{
scanf("%d%d%d%d",&n,&m,&x,&y);
x+=1;
y+=1;
n+=1;
m+=1;
map[x][y]=1;
map[x+2][y+1]=1;
map[x+2][y-1]=1;
map[x+1][y+2]=1;
map[x+1][y-2]=1;
map[x-2][y+1]=1;
map[x-2][y-1]=1;
map[x-1][y+2]=1;
map[x-1][y-2]=1;
/*for(int i=1;i<=n;++i)
{
if(map[i][1]==0)dp[i][1]=1;
}
for(int i=1;i<=m;++i)
{
if(map[1][i]==0)dp[1][i]=1;
}*/
dp[1][1]=1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(map[i][j]!=1&&dp[i][j]==0)dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
printf("%d",dp[n][m]);
return 0;
}
``````
• @ 2017-10-02 16:33:55
``````//注意边界
#include<iostream>
using namespace std;
int map[18][18],pan[18][18],z[18][18],bx[9]={0,1,1,-1,-1,2,2,-2,-2},by[9]={0,2,-2,2,-2,1,-1,1,-1};
int main()
{
int n,m,x,y,i,k;
cin>>n>>m>>x>>y;
for(i=0;i<=8;i++)
{
int nx,ny;
nx=x+bx[i];
ny=y+by[i];
if(nx>=0&&nx<=m&&ny>=0&&ny<=n)
pan[nx][ny]=1;
}
z[0][0]=1;
for(i=0;i<=n;i++)
for(k=0;k<=m;k++)
{
if(i==0&&k==0)
continue;
if(pan[i][k])
continue;
if(i==0)
{
z[i][k]=z[i][k-1];
continue;
}
if(k==0)
{
z[i][k]=z[i-1][k];
continue;
}
z[i][k]=z[i-1][k]+z[i][k-1];
}
cout<<z[n][m];
return 0;
}
``````
• @ 2017-07-18 21:57:45

#include "stdio.h"
#include "stdlib.h"
#include "iostream"

using namespace std;

int main () {
int ma[105][105]={0},wa[105][105]={0},b1,b2,m1,m2,i,j;
int d[2][8]={-2,-2,-1,-1,1,1,2,2,
1,-1,2,-2,2,-2,1,-1};

scanf("%d%d%d%d",&b1,&b2,&m1,&m2);
for(i = 0; i <= 1; i ++)
for(j = 0; j <= 7; j ++) {
ma[m1+d[0][j]][m2+d[1][j]]=1;
}
ma[m1][m2]=1;
wa[0][1]=1;wa[1][0]=1;

for(i = 0; i <= b1; i ++) {
for(j = 0; j <= b2; j ++) {
if((ma[i][j]==0)&&(ma[i][j-1]==0)&&(j-1>=0)) {
wa[i][j]=wa[i][j]+wa[i][j-1];
}
if((ma[i][j]==0)&&(ma[i-1][j]==0)&&(i-1>=0)) {
wa[i][j]=wa[i][j]+wa[i-1][j];
}
/* printf("%d ",wa[i][j]); 注释语句皆为调试语句 /
}
/
printf("\n"); */
}

printf("%d",wa[b1][b2]);
return 0;
}
#include "stdio.h"
#include "stdlib.h"
#include "iostream"

using namespace std;

int main () {
int ma[105][105]={0},wa[105][105]={0},b1,b2,m1,m2,i,j;
int d[2][8]={-2,-2,-1,-1,1,1,2,2,
1,-1,2,-2,2,-2,1,-1};

scanf("%d%d%d%d",&b1,&b2,&m1,&m2);
for(i = 0; i <= 1; i ++)
for(j = 0; j <= 7; j ++) {
ma[m1+d[0][j]][m2+d[1][j]]=1;
}
ma[m1][m2]=1;
wa[0][1]=1;wa[1][0]=1;

for(i = 0; i <= b1; i ++) {
for(j = 0; j <= b2; j ++) {
if((ma[i][j]==0)&&(ma[i][j-1]==0)&&(j-1>=0)) {
wa[i][j]=wa[i][j]+wa[i][j-1];
}
if((ma[i][j]==0)&&(ma[i-1][j]==0)&&(i-1>=0)) {
wa[i][j]=wa[i][j]+wa[i-1][j];
}
/* printf("%d ",wa[i][j]); 注释语句皆为调试语句 /
}
/
printf("\n"); */
}

printf("%d",wa[b1][b2]);
return 0;
}

• @ 2017-07-10 17:35:33

没有判断边界居然AC了。。。

``````#include<cstdio>
#include<cstring>
bool control[21][21];
int bx,by,hx,hy,f[21][21];
int main()
{
memset(f,0,sizeof(f));
f[0][0]=1;
scanf("%d%d%d%d",&bx,&by,&hx,&hy);
control[hx][hy]=1;
control[hx-2][hy-1]=1;control[hx-2][hy+1]=1;control[hx-1][hy+2]=1;control[hx-1][hy-2]=1;
control[hx+2][hy-1]=1;control[hx+2][hy+1]=1;control[hx+1][hy+2]=1;control[hx+1][hy-2]=1;
for(int i=0;i<=bx;i++)
for(int j=0;j<=by;j++)
{
if(i>0&&!control[i][j]) f[i][j]+=f[i-1][j];
if(j>0&&!control[i][j]) f[i][j]+=f[i][j-1];
}
printf("%d\n",f[bx][by]);
return 0;
}
``````

其中计算马的控制点的方法应该是这样比较恰当

``````int x[8]={-2,-2,-1,-1,1,1,2,2};
int y[8]={-1,1,-2,2,-2,2,1,-1};
/*
......
*/
for(i=0;i<8;i++) {
if((y[i]+hy)>=0&&(y[i]+hy)<=20&&(x[i]+hx)>=0&&(x[i]+hx)<=20) {
control[y[i]+hy][x[i]+hx]=1;
}
}
``````
• @ 2017-01-22 15:43:38

#include<iostream>
#include<cstdio>
using namespace std;
int a[20][20];
bool b[20][20];
void f(int x,int c)
{
for(int i=1;i<16;i++)
{
for(int j=1;j<16;j++)
{
if(b[i][j]==1) a[i][j]=a[i-1][j]+a[i][j-1];
}
}
}
int main()
{
int n,m,x,y;
for(int i=0;i<16;i++)
for(int j=0;j<16;j++)
{
a[i][j]=0;b[i][j]=1;
}
scanf("%d%d%d%d",&n,&m,&x,&y);
if(x>=0&&y>=0)b[x][y]=0;
if(x+2<=15&&y+1<=15)b[x+2][y+1]=0;
if(x+2<=15&&y-1>=0)b[x+2][y-1]=0;
if(x+1<=15&&y+2<=15)b[x+1][y+2]=0;
if(x+1<=15&&y-2>=0)b[x+1][y-2]=0;
if(x-1>=0&&y+2<=15)b[x-1][y+2]=0;
if(x-1>=0&&y-2>=0)b[x-1][y-2]=0;
if(x-2>=0&&y+1<=15)b[x-2][y+1]=0;
if(x-2>=0&&y-1>=0)b[x-2][y-1]=0;
for(int i=1;i<=n;i++)
{
if(i==1){if(b[i][0]!=0)a[i][0]=1;}else a[i][0]=a[i-1][0];
}
for(int i=1;i<=m;i++)
{
if(i==1){if(b[0][i]!=0)a[0][i]=1;}else a[0][i]=a[0][i-1];
}
f(n,m);
printf("%d",a[n][m]);
}

• @ 2016-08-26 16:57:25

#include<iostream>
using namespace std;
int a[20][20];
int m,n;
int ass=0;
void find(int x,int y)
{
if((x<0)||(y<0)||(a[x][y]==-1))
{
return;
}
else if(x==0&&y==0)
{
ass++;
return;
}
else
{
find(x-1,y);
find(x,y-1);
}
}
int main()
{
int x,y;
cin>>m>>n>>x>>y;
a[x][y]=-1;
a[x-1][y-2]=-1;
a[x-2][y-1]=-1;
a[x+1][y+2]=-1;
a[x+2][y+1]=-1;
a[x-1][y+2]=-1;
a[x-2][y+1]=-1;
a[x+1][y-2]=-1;
a[x+2][y-1]=-1;
find(m,n);
cout<<ass;
return 0;
}

• @ 2016-08-16 19:42:52
• @ 2016-08-15 14:54:48

const

dx:array[1..8] of integer=(2,1,-1,-2,-2,-1,1,2);

dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);

var

f:array[0..20,0..20] of longint;

g:array[-2..22,-2..22] of boolean;

i,j,n,m,x,y:integer;

begin

fillchar(g,sizeof(g),true);

g[x,y]:=false;

for i:=1 to 8 do g[x+dx[i],y+dy[i]]:=false;

if g[0,0] then f[0,0]:=1;

for j:=1 to m do

if g[0,j] then f[0,j]:=f[0,j-1];

for i:=1 to n do

if g[i,0] then f[i,0]:=f[i-1,0];

for i:=1 to n do

for j:=1 to m do

if g[i,j] then f[i,j]:=f[i-1,j]+f[i,j-1];

writeln(f[n,m]);

end.

• @ 2016-08-01 11:16:54

#include<bits/stdc++.h>
using namespace std;
int opt[17][17]={0};
bool _map[17][17];
int dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};
int main()
{
int ex,ey,mx,my,nx,ny,i,j;
memset(_map,false,sizeof(_map));
cin>>ex>>ey>>mx>>my;
ex++;
ey++;
mx++;
my++;
for(i=1;i<=ex;i++)
for(j=1;j<=ey;j++)
_map[i][j]=true;
_map[mx][my]=false;
for(i=1;i<=ex;i++)
opt[i][1]=1;
for(i=1;i<=ey;i++)
opt[1][i]=1;
for(i=0;i<8;i++)
{
nx=mx+dx[i];
ny=my+dy[i];
if(nx>=1&&nx<=ex&&ny>=1&&ny<=ey)
{
_map[nx][ny]=false;
opt[nx][ny]=0;
}
}
if(mx==1)
{
for(i=my;i<=ey;i++)
opt[1][i]=0;
}
if(my==1)
{
for(i=mx;i<=ex;i++)
opt[i][1]=0;
}
for(i=1;i<=ex;i++)
for(j=1;j<=ey;j++)
if(i==1&&j==1) continue;
else if(_map[i][j]) opt[i][j]=opt[i-1][j]+opt[i][j-1];
// for(i=1;i<=ex;i++)
// {
// for(j=1;j<=ey;j++)
// if(i==mx&&j==my) cout<<"@"<<" ";
// else cout<<opt[i][j]<<" ";
// cout<<endl;
// }
cout<<opt[ex][ey]<<endl;
return 0;
}

ID
1121

4

9575

3782

39%

23