有个走迷宫的结论。排列组合那块数学可能有涉及。到达这个点的路径数等于他左边的路径数和上面的路径数。可以凭此建立递推，递归，动态规划的式子。因此解法很多。

我这里用的是递归。边界条件是坐标点（0,0）（方法数为1）以及棋盘外所有延伸出去的每一个点（方法数为0）

递推和动态规划差不多一个思路。可以拿来研究练手不错。
###pascal code
program P1121;
var can:array[-2..18,-2..18] of longint;
x,y,n,m,i,j,ans:longint;
function main(a,b:longint):longint;
begin
if can[a,b]=1 then begin main:=0; exit; end;
if (a=0) and (b=0) then begin main:=1; exit; end;
if (b=-1) then begin main:=0; exit; end;
if (a=-1) then begin main:=0; exit; end;
main:=main(a-1,b)+main(a,b-1);
end;

begin //main
read(n,m); read(x,y); fillchar(can,sizeof(can),0);
can[x,y]:=1;
can[x-2,y-1]:=1; can[x+2,y-1]:=1; can[x+1,y-2]:=1; can[x-1,y-2]:=1;
can[x-1,y+2]:=1; can[x+1,y+2]:=1; can[x+2,y+1]:=1; can[x-2,y+1]:=1;
ans:=main(n,m);
write(ans);
end.

#include <iostream>

using namespace std;

void setPoint(int table[17][17], int x, int y, int terX, int terY){
if(x >= 1 && x <= terX && y >=1 && y <= terY)
table[x][y] = -1;
}

int main(){
int terX,terY,horseX,horseY;
cin >> terX >> terY >> horseX >> horseY;
terX++;terY++;horseX++;horseY++;
int table[17][17]={0};
table[1][1] = 1;
setPoint(table,horseX,horseY,terX,terY);
setPoint(table,horseX - 2,horseY - 1,terX,terY);
setPoint(table,horseX - 1,horseY - 2,terX,terY);
setPoint(table,horseX - 2,horseY + 1,terX,terY);
setPoint(table,horseX - 1,horseY + 2,terX,terY);
setPoint(table,horseX + 2,horseY - 1,terX,terY);
setPoint(table,horseX + 1,horseY - 2,terX,terY);
setPoint(table,horseX + 2,horseY + 1,terX,terY);
setPoint(table,horseX + 1,horseY + 2,terX,terY);
for(int x = 1; x <= terX; x++){
for(int y = 1; y <=terY; y++){
if(x == 1 && y == 1) continue;
if(table[x][y] == -1) continue;
if(table[x-1][y] == -1 && table[x][y-1] == -1){
table[x][y] = 0;
continue;
}
if(table[x-1][y] == -1){
table[x][y] = table[x][y-1];
continue;
}
if(table[x][y-1] == -1){
table[x][y] = table[x-1][y];
continue;
}
table[x][y] = table[x-1][y] + table[x][y-1];
}
}
cout << table[terX][terY] << endl;
}

/*************************************************************************
> File Name: 1121.cpp
> Author: Netcan
> Blog: http://www.netcan.xyz
> Mail: 1469709759@qq.com
> Created Time: Fri 01 May 2015 21:41:30 CST
************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int main()
{
int Bx, By, Hx, Hy;
static bool map[20][20];
static int dp[20][20];
while(scanf("%d%d%d%d", &Bx, &By, &Hx, &Hy) == 4) {
memset(map, 1, sizeof(map));
map[Hy][Hx] = map[Hy-2][Hx-1] = map[Hy-2][Hx+1] = map[Hy+2][Hx-1] = map[Hy+2][Hx+1] = false;
map[Hy-1][Hx-2] = map[Hy-1][Hx+2] = map[Hy+1][Hx-2] = map[Hy+1][Hx+2] = false;

// for(int i=0; i<=Bx; ++i) {
// for(int j=0; j<=By; ++j) {
// cout << map[i][j] << " ";
// }
// cout << endl;
// }

memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int j=0; j<=By; ++j)
for(int i=0; i<=Bx; ++i) {
if(map[j][i]) {
if(i>0 && j>0)
dp[j][i] = dp[j-1][i] + dp[j][i-1];
if(j>0 && i==0)
dp[j][i] = dp[j-1][i];
if(i>0 && j==0)
dp[j][i] = dp[j][i-1];

}
else
dp[j][i] = 0;
}
printf("%d\n", dp[By][Bx]);
}
return 0;
}

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define sz 20
#define LL long long
#define for1(v,a,b) for (int v=a;v<=b;v++)
#define for2(v,a,b) for (int v=a;v>=b;v--)
using namespace std;
int n,m,s,t;
bool map[sz][sz];
int f[sz][sz];
void doing(int x,int y){
if ((x>=0)&&(x<=n)&&(y>=0)&&(y<=m))
map[x][y]=false;
}
void Init(){
doing(s-1,t-2);
doing(s-1,t+2);
doing(s-2,t-1);
doing(s-2,t+1);
doing(s+1,t-2);
doing(s+1,t+2);
doing(s+2,t-1);
doing(s+2,t+1);
for1(i,0,n)
if (map[i][0]) f[i][0]=1;
else break;
for1(i,0,m)
if (map[0][i]) f[0][i]=1;
else break;
}
int main(){
//freopen("p1.in","r",stdin);
memset(map,true,sizeof(map));
scanf("%d%d",&n,&m);
scanf("%d%d",&s,&t);
map[s][t]=false;
Init();
if (!map[0][0]){
printf("0");
return 0;
}
for1(i,1,n)
for1(j,1,m)
if (map[i][j]) f[i][j]=f[i-1][j]+f[i][j-1];
printf("%d",f[n][m]);
return 0;
}

D(di)P(tui)，\(f(i,j)\)表示从\((0,0)\)到\((i,j)\)的路径数，如果是控制点的话\(f(i,j)=0\)，否则\(f(i,j)=f(i-1,j)+f(i,j-1)\)。
采用常量数组可以简化编写。

Pascal Code

const
dx:array[1..9] of longint=(-2,2,-2,2,-1,1,-1,1,0);
dy:array[1..9] of longint=(1,-1,-1,1,2,-2,-2,2,0);
var
a,b:array[-3..20,-3..20] of longint;
n,m,x,y,i,j:longint;
begin
readln(x,y,n,m);
fillchar(a,sizeof(a),0);
filldword(b,sizeof(b) div 4,1);
for i:=1 to 9 do
b[n+dx[i],m+dy[i]]:=0;
a[0,0]:=1*b[0,0];
for i:=0 to x do
for j:=0 to y do
begin
if (i=0) and (j=0) then continue;
a[i,j]:=(a[i-1,j]+a[i,j-1])*b[i,j];
end;
writeln(a[x,y]);
end.

#include <iostream>
using namespace std;
int fal[17][17];
void horse(int x, int y);
int main(){
int bx, by, mx, my;
cin >> bx >> by >> mx >> my;
for (int i = 1; i <= bx + 1; i++){
for (int j = 1; j <= by + 1; j++){
fal[i][j] = 1;
}
}
horse(mx + 1, my + 1);
for (int i = 1; i <= bx + 1; i++){
for (int j = 1; j <= by + 1; j++){
if (i == 1 && j == 1)continue;
if (fal[i][j]){
fal[i][j] = fal[i - 1][j] + fal[i][j - 1];
}
}
}
cout << fal[bx + 1][by + 1] << endl;
}
void horse(int x, int y){
fal[x][y] = 0;
fal[x - 1][y - 2] = 0;
fal[x - 1][y + 2] = 0;
fal[x + 1][y - 2] = 0;
fal[x + 1][y + 2] = 0;
fal[x - 2][y - 1] = 0;
fal[x - 2][y + 1] = 0;
fal[x + 2][y - 1] = 0;
fal[x + 2][y + 1] = 0;

}

DP完解
到达当前点的路径数 = 到达这个点左边的点的路径数 + 到达这个点右边的点的路径数

###Traveller_C's Code
/*
Author: Traveller_C
PROG: vijos 1121
DATE: 2015.2.4
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#define REP(i,n) for(int i=1;i<=n;i++)
#define REP_(i,n) for(int i=0;i<=n;i++)
#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

/*void setIO(string a)
{
string in=a+".in",out=a+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}*/

const int MAX_N=1005;

int Xb,Yb,Xh,Yh;
bool map[MAX_N][MAX_N];

void In_Pre()
{
scanf("%d %d %d %d",&Xb,&Yb,&Xh,&Yh);

CLR(map,1);
map[Xh][Yh]=0;
map[Xh-1][Yh-2]=map[Xh+1][Yh-2]=map[Xh-2][Yh-1]=map[Xh+2][Yh-1]=0;
map[Xh-2][Yh+1]=map[Xh+2][Yh+1]=map[Xh-1][Yh+2]=map[Xh+1][Yh+2]=0;
}

int f[MAX_N][MAX_N];

void Do_Out()
{
CLR(f,0);
f[0][0]=1;

REP_(i,Xb){
REP_(j,Yb){
if(!map[i][j]) f[i][j]=0;
else{
if(i>0&&j==0) f[i][j]=f[i-1][j];
if(j>0&&i==0) f[i][j]=f[i][j-1];
if(i>0&&j>0) f[i][j]=f[i-1][j]+f[i][j-1];
}
}
}

/*REP(i,Xb){
REP(j,Yb) printf("%d ",f[i][j]);
printf("\n");
}*/

printf("%d\n",f[Xb][Yb]);
}

int main()
{
//setIO("vijos1121");
In_Pre();
Do_Out();
return 0;
}

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

__int64 a[20][20];
bool b[20][20];
int x,y,n,m;

void avoid();

int main()
{
int i,j;
scanf("%d%d%d%d",&n,&m,&x,&y);
memset(a,0,sizeof(a));
memset(b,true,sizeof(b));
avoid();
a[0][0]=1;
for (i=0;i<=n;i++)
for (j=0;j<=m;j++)
{
if (i>0 && b[i-1][j])
a[i][j]+=a[i-1][j];
if (j>0 && b[i][j-1])
a[i][j]+=a[i][j-1];
}
printf("%I64d\n",a[n][m]);
return 0;
}

void avoid()
{
b[x][y]=false;

b[x-2][y-1]=false;
b[x-2][y+1]=false;
b[x-1][y-2]=false;
b[x-1][y+2]=false;

b[x+2][y-1]=false;
b[x+2][y+1]=false;
b[x+1][y-2]=false;
b[x+1][y+2]=false;
}

求解

我不会

飞 愤怒 vv想 v出现

测试数据 #0: Accepted, time = 15 ms, mem = 8336 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 8332 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 8336 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 8336 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 8336 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 8336 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 8332 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 8336 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 8336 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 8332 KiB, score = 10
Accepted, time = 60 ms, mem = 8336 KiB, score = 100

#include<iostream>
#include<cstdio>
const int maxh=1000;
long long int f[maxh][maxh]={0};
int bh,bl;
int hh,hl;
using namespace std;
int main()
{
int a,b;
scanf("%d%d%d%d",&bl,&bh,&hl,&hh);
f[hh+1][hl+2]=-1;
f[hh+1][hl-2]=-1;
f[hh-1][hl+2]=-1;
f[hh-1][hl-2]=-1;
f[hh+2][hl+1]=-1;
f[hh+2][hl-1]=-1;
f[hh-2][hl+1]=-1;
f[hh-2][hl-1]=-1;
f[hh][hl]=-1;
for(int i=1;i<=bh;i++)
{
if(f[i][0]==-1)
break;

f[i][0]=1;
}
for(int i=1;i<=bl;i++)
{
if(f[0][i]==-1)
break;
f[0][i]=1;
}
for(int i=1;i<=bh;i++)
for(int j=1;j<=bl;j++)
{
if(f[i][j]!=-1)
{
if(f[i][j-1]!=-1&&f[i-1][j]!=-1)
f[i][j]=f[i][j-1]+f[i-1][j];
else if(f[i][j-1]==-1)
f[i][j]=f[i-1][j];
else if(f[i-1][j]==-1)
f[i][j]=f[i][j-1];
}
}
printf("%lld\n",f[bh][bl]);
return 0;
}
第三点初始化要加特判。。。被坑好久

var
a:array[-2..15,-2..15]of longint;
b:array[-2..15,-2..15]of boolean;
i,j,n,m,x,y:longint;
begin
read(n,m,x,y);b[x,y]:=true;
b[x+2,y+1]:=true;b[x-2,y+1]:=true;b[x+2,y-1]:=true;b[x-2,y-1]:=true;
b[x+1,y+2]:=true;b[x-1,y+2]:=true;b[x+1,y-2]:=true;b[x-1,y-2]:=true;
for i:=1 to n do if not b[i,0] then a[i,0]:=1 else break;
for i:=1 to m do if not b[0,i] then a[0,i]:=1 else break;
for i:=1 to n do for j:=1 to m do
if not b[i,j] then a[i,j]:=a[i,j-1]+a[i-1,j];
writeln(a[n,m]);
end.
告诉你们什么是简练

#include<cstring>
#include<iostream>
using namespace std;
main()
{
int bx,by,mx,my,i,j;
cin>>bx>>by>>mx>>my;
long long a[bx+1][by+1],m[bx+1][by+1];
memset(a,0,sizeof(a));
memset(m,0,sizeof(m));
a[0][0]=m[mx+1][my+2]=m[mx+1][my-2]=m[mx+2][my+1]=m[mx+2][my-1]=m[mx-1][my-2]=m[mx-1][my+2]=m[mx-2][my+1]=m[mx-2][my-1]=m[mx][my]=1;
for(i=0;i<=bx;i++)
for(j=0;j<=by;j++)
{
if(i>=1&&m[i][j]==0)
a[i][j]+=a[i-1][j];
if(j>=1&&m[i][j]==0)
a[i][j]+=a[i][j-1];
}
cout<<a[bx][by];
}

#include<iostream>

using namespace std;
int main()
{
int bx,by,mx,my;
cin>>bx>>by>>mx>>my;
long long a[bx+1][by+1],m[bx+1][by+1];
for(int i=0;i<=bx;i++)
for(int j=0;j<=by;j++)
{
a[i][j]=0;
m[i][j]=0;
}
a[0][0]=1;
m[mx+1][my+2]=1;
m[mx+1][my-2]=1;
m[mx+2][my+1]=1;
m[mx+2][my-1]=1;
m[mx-1][my-2]=1;
m[mx-1][my+2]=1;
m[mx-2][my+1]=1;
m[mx-2][my-1]=1;
m[mx][my]=1;
for(int i=0;i<=bx;i++)
for(int j=0;j<=by;j++)
{
if(i>=1&&m[i][j]==0)
a[i][j]+=a[i-1][j];
if(j>=1&&m[i][j]==0)
a[i][j]+=a[i][j-1];
}
cout<<a[bx][by];
}

#include<iostream>
using namespace std;
int main()
{
int bx,by,mx,my;//x-y|
cin>>bx>>by>>mx>>my;
long long a[bx+1][by+1],m[bx+1][by+1];
for(int i=0;i<=bx;i++)
for(int j=0;j<=by;j++)
{a[i][j]=0;m[i][j]=0;}
a[0][0]=1;
m[mx+1][my+2]=1;
m[mx+1][my-2]=1;
m[mx+2][my+1]=1;
m[mx+2][my-1]=1;
m[mx-1][my-2]=1;
m[mx-1][my+2]=1;
m[mx-2][my+1]=1;
m[mx-2][my-1]=1;
m[mx][my]=1;
for(int i=0;i<=bx;i++)
for(int j=0;j<=by;j++)
{
if(i>=1&&m[i][j]==0)
a[i][j]+=a[i-1][j];
if(j>=1&&m[i][j]==0)
a[i][j]+=a[i][j-1];
}
cout<<a[bx][by];
}

program Project1;
var
map,date:array[-3..20,-3..20] of longint;
i,j,m,n,a,b,x,y:longint;
begin
readln(m,n,a,b);
for i:=-3 to 20 do
for j:=-3 to 20 do map[i,j]:=0;
for i:=0 to m do
for j:=0 to n do map[i,j]:=1;
map[a,b]:=0;
map[a+1,b+2]:=0;
map[a+1,b-2]:=0;
map[a+2,b+1]:=0;
map[a+2,b-1]:=0;
map[a-1,b-2]:=0;
map[a-1,b+2]:=0;
map[a-2,b+1]:=0;
map[a-2,b-1]:=0;
date[0,0]:=1;
for i:=0 to m do
for j:=0 to n do
if map[i,j]=1 then
begin
if map[i-1,j]=1 then x:=1;
if map[i,j-1]=1 then y:=1;
if (x=1)and(y=1) then date[i,j]:=date[i-1,j]+date[i,j-1];
if (x=1)and(y=0) then date[i,j]:=date[i-1,j];
if (x=0)and(y=1) then date[i,j]:=date[i,j-1];
end;
writeln(date[m,n]);
end.

求解 求解 啊啊啊啊啊啊啊

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

#include<cstdio>
#include<cstdlib>
#include<cmath>
#define max(a,b) a>b?a:b
typedef long long int longint;
using namespace std;
longint pic[20][20];
longint a,b,m,n;
int xxx(){
pic[m][n]=0;
for(longint x=-2;x<=2;x++){
if(x){
longint b1=3-abs(x),b2=-b1;
if(m+x>=0){
if(n+b1>=0) pic[m+x][n+b1]=0;
if(n+b2>=0) pic[m+x][n+b2]=0;
}
}
}
int i;
for(i=0;i<=a;i++) if(!pic[i][0]) break;
for(;i<=a;i++) pic[i][0]=0;
for(i=0;i<=b;i++) if(!pic[0][i]) break;
for(;i<=b;i++) pic[0][i]=0;
return 0;
}
int main(){
scanf("%I64d %I642d %I64d %I64d",&a,&b,&m,&n);
if(m+n==0||(m==2&&n==0)||(m==a&&n==b)) {printf("0");return 0;}
for(longint i=0;i<=19;i++)for(longint j=0;j<=19;j++)pic[i][j]=1;
xxx();
for(longint i=1;i<=a;i++)for(longint j=1;j<=b;j++){
if(pic[i][j])
pic[i][j]=pic[i-1][j]+pic[i][j-1];
}
printf("%I64d ",pic[a][b]);
return 0;
}