求大大看看 错哪了 提交上去是RE 改了好多次实在是没办法了 求指导
求大大看看 哪里错了 提交上去是RE 改了好多次实在是没办法了 求指导
Description
A点有一个卒，需要走到目标B点。行走规则：可以向下或者向右。要求计算从A能够到达B的路径的条数，并输出每一条路径。
Input
输入A点的坐标(ax,ay)和B点的坐标(bx,by),
(|ax-bx|<=10且|ay-by|<=10).
Output
按照规定顺序输出路径(一行一条).
最后输出路径数.
如:
(1,3)->(2,3)->(2,4)和(1,3)->(1,4)->(2,4)两条路径
那么输出顺序为
(1,3)->(1,4)->(2,4)
(1,3)->(2,3)->(2,4)
既先按x升序,再按y升序.
具体见样例.
Sample Input
1 1 4 3
Sample Output
(1,1)-->(1,2)-->(1,3)-->(2,3)-->(3,3)-->(4,3)
(1,1)-->(1,2)-->(2,2)-->(2,3)-->(3,3)-->(4,3)
(1,1)-->(1,2)-->(2,2)-->(3,2)-->(3,3)-->(4,3)
(1,1)-->(1,2)-->(2,2)-->(3,2)-->(4,2)-->(4,3)
(1,1)-->(2,1)-->(2,2)-->(2,3)-->(3,3)-->(4,3)
(1,1)-->(2,1)-->(2,2)-->(3,2)-->(3,3)-->(4,3)
(1,1)-->(2,1)-->(2,2)-->(3,2)-->(4,2)-->(4,3)
(1,1)-->(2,1)-->(3,1)-->(3,2)-->(3,3)-->(4,3)
(1,1)-->(2,1)-->(3,1)-->(3,2)-->(4,2)-->(4,3)
(1,1)-->(2,1)-->(3,1)-->(4,1)-->(4,2)-->(4,3)
10
HINT
由于输出庞大
请不要用cout
请用printf
------解决方案--------------------
这个问题可以用回溯法来解。可以把它作为学习回溯法的一个好示例。
记A的坐标为(Xa,Ya), B的坐标为(Xb,Yb),其中Xb>=Xa, Yb>=Ya. 那么一条合法完整的路径的长度等于Xb+Yb-Xa-Ya, 记n=Xb+Yb-Xa-Ya.
取一个长度为Xb+Yb-Xa-Ya的Point数组。每个位置最多有向上和向右两种选择，这是一个状态空间不大于2^n的子集树搜索问题。
Description
A点有一个卒，需要走到目标B点。行走规则：可以向下或者向右。要求计算从A能够到达B的路径的条数，并输出每一条路径。
Input
输入A点的坐标(ax,ay)和B点的坐标(bx,by),
(|ax-bx|<=10且|ay-by|<=10).
Output
按照规定顺序输出路径(一行一条).
最后输出路径数.
如:
(1,3)->(2,3)->(2,4)和(1,3)->(1,4)->(2,4)两条路径
那么输出顺序为
(1,3)->(1,4)->(2,4)
(1,3)->(2,3)->(2,4)
既先按x升序,再按y升序.
具体见样例.
Sample Input
1 1 4 3
Sample Output
(1,1)-->(1,2)-->(1,3)-->(2,3)-->(3,3)-->(4,3)
(1,1)-->(1,2)-->(2,2)-->(2,3)-->(3,3)-->(4,3)
(1,1)-->(1,2)-->(2,2)-->(3,2)-->(3,3)-->(4,3)
(1,1)-->(1,2)-->(2,2)-->(3,2)-->(4,2)-->(4,3)
(1,1)-->(2,1)-->(2,2)-->(2,3)-->(3,3)-->(4,3)
(1,1)-->(2,1)-->(2,2)-->(3,2)-->(3,3)-->(4,3)
(1,1)-->(2,1)-->(2,2)-->(3,2)-->(4,2)-->(4,3)
(1,1)-->(2,1)-->(3,1)-->(3,2)-->(3,3)-->(4,3)
(1,1)-->(2,1)-->(3,1)-->(3,2)-->(4,2)-->(4,3)
(1,1)-->(2,1)-->(3,1)-->(4,1)-->(4,2)-->(4,3)
10
HINT
由于输出庞大
请不要用cout
请用printf
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct success_step
{
int step1[21];
int sum;
}ss[10000];
int cmp(const void *a,const void *b)
{
struct success_step *p=(struct success_step *)a;
struct success_step *q=(struct success_step *)b;
return q->sum-p->sum;
}
int main()
{
int ax,ay,bx,by;
int step[21];
int max,i=0,j,x,y,k=0,xi,yi,j1,n,m;
scanf("%d%d%d%d",&ax,&ay,&bx,&by);
max=by+bx-ax-ay;
x=bx-ax;y=by-ay;k=0;
for(j=0;j<max;j++)
step[j]=0;
while(i!=max)//列举出 可能的 移动方式
{
i=0;xi=0;yi=0;n=0;
while(i<max&&++step[i]==2)
{
step[i++]=0;
}
for(j=0;j<max;j++)
if(step[j]==0)xi++;
else yi++;
if(xi==x&&yi==y)
{
for(j=0,j1=max;j<max;j1--,j++){
ss[k].step1[j]=step[j];
if(step[j]==1)n+=pow(2,j1);
}
ss[k++].sum=n;
}
}
qsort(ss,k,sizeof(ss[0]),cmp);//排序 先x后y
for(i=0;i<k;i++)//打印
{
xi=ax;yi=ay;
printf("(%d,%d)-->",ax,ay);
for(j=0;j<max;j++){
if(ss[i].step1[j]==0)xi++;
else yi++;
if(j!=max-1)printf("(%d,%d)-->",xi,yi);
else printf("(%d,%d)\n",xi,yi);
}
}
printf("%d\n",k);
return 0;
}
------解决方案--------------------
这个问题可以用回溯法来解。可以把它作为学习回溯法的一个好示例。
记A的坐标为(Xa,Ya), B的坐标为(Xb,Yb),其中Xb>=Xa, Yb>=Ya. 那么一条合法完整的路径的长度等于Xb+Yb-Xa-Ya, 记n=Xb+Yb-Xa-Ya.
取一个长度为Xb+Yb-Xa-Ya的Point数组。每个位置最多有向上和向右两种选择，这是一个状态空间不大于2^n的子集树搜索问题。
struct point{ int x,y; };
point steps[n];
void back_track(int i)
{
if(i==n)
{
// we get a path in steps, output it
output_path();
return;
}
steps[i]=steps[i-1]; //复制前面点的位置，后面修改
// 向右，如果可行