帮忙看一道题，类似于迷宫求解.该怎么解决

帮忙看一道题，类似于迷宫求解.

C/C++ code

习题 158：奇怪的车子★★★题目描述：有一辆奇怪的车子，因为它的方向盘坏了，它只能选择向前直走或者向右拐。现在这辆车处在一个w*h大小的网格的(0,0)的地方（左上角），它需要到网格里的另一地点(x,y)，并且每一次它不能走自己之前走过的地方问有多少种不同的方案呢？输入：多组测试数据，每行四个数w,h,x,y (1 <= w,h <= 4000，且 0 <= x < w， 0 <= y < h)输出：输出总的方案数，因为结果可能很巨大，为避免大整数运算，结果对10000取模输出就行了样例输入：1 1 0 03 3 1 14 4 1 14 3 2 110 10 5 520 20 10 10样例输出：14115944670其它信息：20 20 10 10这一组的完整结果是3903970070难度：Normal

C/C++ code

#include <iostream>using namespace std;enum Flag {VISITED,NOT_VISITED};Flag martrix[50][50];//标记是否路过const int turn[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//行走方向,右,下,左,上.int w,h,x,y;//输入信息,w表示横向x，h表示纵向yint dx,dy;//当前位置int count;//总路径void count_paths(int direction=0);//计算总路径bool test_turn(int,int,int);//检测可否转弯bool test_forward(int,int,int);//检测可否前进void initiate();void count_paths(int direction){    //达到目的地    if(dx==x&&dy==y)    {        ++count;        return;    }    //标记访问    martrix[dx][dy]=VISITED;    int temp=direction;    //拐弯判定 (+1)    if(test_turn((direction+1)%4,dx,dy))    {        direction=(direction+1)%4;        dx+=turn[direction][0];        dy+=turn[direction][1];        count_paths(direction);        dx-=turn[direction][0];        dy-=turn[direction][1];        direction=temp;    }    //直线前进检测 (+0)    if(test_forward(direction,dx,dy))    {        dx+=turn[direction+0][0];        dy+=turn[direction+0][1];        count_paths(direction);        dx-=turn[direction+0][0];        dy-=turn[direction+0][1];    }    martrix[dx][dy]=NOT_VISITED;}bool test_turn(int dir,int loc_x,int loc_y)//拐弯检测{    switch(dir)    {    case 0: return loc_y<=y; break;    case 1: return loc_x>=x; break;    case 2: return loc_y>=y; break;    case 3: return loc_x<=x; break;    default:return false;break;    }}bool test_forward(int dir,int loc_x,int loc_y)//前进检测{    int to_x=loc_x+turn[dir][0];    int to_y=loc_y+turn[dir][1];    return (to_x>=0)&&(to_y>=0)&&(to_x<=w-1)&&(to_y<=h-1)&&(martrix[to_x][to_y]==NOT_VISITED);}void initiate()//初始化{    count=0;    //起始点一定是在(x,y)点的正上方，即(x,0)    dx=x;    dy=0;    for(int i=0;i<=x;++i)    {        martrix[i][0]=VISITED;//对从(0,0)到(x,0)这段路标记已访问    }        count_paths();    cout<<count;    for(int i=0;i<=x;++i)    {        martrix[i][0]=NOT_VISITED;    }}int main(){    for(int i=0;i<50;++i)    {        for(int j=0;j<50;++j)        {            martrix[i][j]=NOT_VISITED;        }    }    while(true)    {        cin>>w>>h>>x>>y;        initiate();    }    return 0;}

这是我写的回溯法,通过拐点检测和前进检测限制了一下,但是当规模达到20*20，解空间仍然很大，没法运行，是不是有什么别的办法。

[解决办法]
动态规划分解子问题看看。。。

[解决办法]
的确定是DP，从上到下，从左到右，每个节点都只有两个分枝!!!!
[解决办法]

探讨

的确定是DP，从上到下，从左到右，每个节点都只有两个分枝!!!!

[解决办法]
先求出最外围一圈的，然后从终点BFS配合DP应该就可以。（考虑的不太仔细，也许有错误）


[解决办法]
哎 ！ 做算法题真伤脑细胞 ！ 
在这里我只是提下建议 ：
建个栈struct 或 class ；
运用贪心算法 。
[解决办法]

探讨

哎 ！ 做算法题真伤脑细胞 ！
在这里我只是提下建议 ：
建个栈struct 或 class ；
运用贪心算法 。

[解决办法]
建立一个Path类，记录路径，每到一个点Clone一个自己。
[解决办法]
不好意思，想简单了，应该按照拐弯的次数来统计，以4 4 1 1为例，最多拐4次，最少1次，次数分别为
4 4 2 1，具体拐4次的线路个数，可以通过组合来算应当是c(1,1) * c(2,1) * c(2,1) * c(1,1)，选择的个数分别对应终点上下左右边的数量。

以20 20 10 10为例，拐12次，12/4 = 3 大概是C(10,3) * C(10,3) * c(10,3) * C(10,3)
[解决办法]
以10 10 5 5为例，LZ先从拐1次想起，只有一个方案，拐2次呢？5种方案，C(5,1)，拐3次，25种，C(5,1) * C(5,1)，拐4次125，5次500，因为向上那条路已经被走过了......

查看更多 下一篇