3008 - c
时间限制 : 1 秒
内存限制 : 128 MB
有一个美丽的池塘。这个长方形的池子被分成了 M 行 N 列个方格（1≤M,N≤30）。一
些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。
贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花
跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。 贝西的舞步很像象棋中的马步：
每次总是先横向移动 M1 (1≤M1≤30)格，再纵向移动 M2 (1≤M2≤30,M1≠M2)格，或先纵
向移动 M1 格，再横向移动 M2 格。最多时，贝西会有八个移动方向可供选择。
给定池塘的布局和贝西的跳跃长度，请计算贝西从起点出发，到达目的地的跳的最小舞
步数，保证输入数据中的目的地一定是可达的。
题目输入
第一行：四个用空格分开的整数：M，N，M1 和 M2
第二行到 M+1 行：第 i+1 行有 N 个用空格分开的整数，描述了池塘第 i 行的状态：0 为水，
1 为莲花，2 为岩石，3 为贝西所在的起点，4 为贝西想去的终点
题目输出
第一行：从起点跳到终点的最少舞步数
输入/输出样例
输入格式
4 5 1 2 1 0 1 0 1 3 0 2 0 4 0 1 2 0 0 0 0 0 1 0
输出格式
2
C++解答
#include<cstdio> #include<queue> #include<cstring> using namespace std; int a[40][40]; int f[40][40]; int m,n,m1,m2; queue<int> q; queue<int> p; int si,sj,ei,ej; int b[8],d[8]; int main() { memset(f,0x7f,sizeof(f)); scanf("%d%d%d%d",&m,&n,&m1,&m2); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); if(a[i][j]==3) { si=i; sj=j; } if(a[i][j]==4) { ei=i; ej=j; } } b[1]=m1;b[2]=m1;b[3]=m2;b[4]=m2;b[5]=-m1;b[6]=-m1;b[7]=-m2;b[8]=-m2; d[1]=m2;d[2]=-m2;d[3]=m1;d[4]=-m1;d[5]=-m2;d[6]=m2;d[7]=-m1;d[8]=m1; q.push(si); p.push(sj); f[si][sj]=0; while(!q.empty() && !p.empty()) { for(int i=1;i<=8;i++) { int x=q.front()+b[i]; int y=p.front()+d[i]; if( ( a[x][y]==1 || a[x][y]==4 ) && x>0 && y>0 && x<=m && y<=n ) { q.push(x); p.push(y); f[x][y]=min(f[x][y],f[q.front()][p.front()]+1); if(a[x][y]==4) { printf("%d",f[x][y]); return 0; } a[x][y]=0; } } q.pop(); p.pop(); } }