谁能帮我用递归解决这个问题？

Question

问题是:有两匹马，白马和黑马，它们的移动方式就像普通国际象棋游戏中马的移动方式一样。我们的目标是找出黑马和白马是否可以相遇(具有相同的位置)。每匹马的移动都有限制。

-用户首先必须输入测试用例的数量。

-第二个用户输入是黑马的起始坐标ex:A1和白马的起始坐标ex:H8。

-最终的用户输入是每匹马移动的限制。例如，如果用户输入 3，则每匹白马和黑马都有 3 次移动的机会。

-输出将为“YES”或“NO”>>>> 如果黑白可以相遇则为 YES，如果不能相遇则为 NO

有人要求我用递归解决这个问题，但我被困住了。

这是一些示例:

输入:

2(案例数量)

A1 H8(坐标)

3(限制移动)

A1 H8(第二个案例的坐标)

1(第二种情况的限制移动)

输出:

案例#1:是

情况#2:否

任何人都可以发现问题或逻辑缺陷..

#include <stdio.h>

int counter=0;
int count[10][10] = {{}};
void moveblack(int black_x,int black_y,int limitblack,int map[10][10],int limit){
//  printf("\n%d,%d\n",black_x,black_y);
//  printf("\n%d\n",limitblack);
//  limitblack++;

    if(limitblack > limit){
        limitblack =0;
        return;
    }
    count[black_y][black_x]++;
    map[black_y][black_x] = 1;
    if(black_x > 8 || black_y > 8 || black_x < 1 || black_y < 1){
        return;
    }
    else{
        //BLACK MOVE
        if(map[black_y+2][black_x+1] == 0){
            moveblack(black_x+1,black_y+2,limitblack+1,map,limit);  
        }
        if(map[black_y+2][black_x-1] == 0){
            moveblack(black_x-1,black_y+2,limitblack+1,map,limit);  
        }
        if(map[black_y-2][black_x+1] == 0){
            moveblack(black_x+1,black_y-2,limitblack+1,map,limit);  
        }   
        if(map[black_y-2][black_x-1] == 0){
            moveblack(black_x-1,black_y-2,limitblack+1,map,limit);  
        }
        if(map[black_y+1][black_x+2] == 0){
            moveblack(black_x+2,black_y+1,limitblack+1,map,limit);  
        }
        if(map[black_y+1][black_x-2] == 0) {
            moveblack(black_x-2,black_y+1,limitblack+1,map,limit);  
        }
        if(map[black_y-1][black_x+2] == 0){
            moveblack(black_x+2,black_y-1,limitblack+1,map,limit);  
        }   
        if(map[black_y-1][black_x-2] == 0){
            moveblack(black_x-2,black_y-1,limitblack+1,map,limit);  
        }
    }   
}
void movewhite(int white_x, int white_y,int limitwhite,int map[10][10],int limit){
//  limitwhite++;
    count[white_y][white_x]++;
    map[white_y][white_x] = 1;
    if(white_x > 8 || white_y > 8 || white_x < 1 || white_y < 1 ){
        return;
    }
    if(limitwhite > limit){
        limitwhite =0;
        return;
    }
    else{
        //WHITE MOVE
        if(map[white_y+2][white_x+1]==0){
            movewhite(white_x+1,white_y+2,limitwhite+1,map,limit);
        }
        if(map[white_y+2][white_x-1]==0){
            movewhite(white_x-1,white_y+2,limitwhite+1,map,limit);
        }   
        if(map[white_y-2][white_x+1]==0){
            movewhite(white_x+1,white_y-2,limitwhite+1,map,limit);
        }   
        if(map[white_y-2][white_x-1]==0){
            movewhite(white_x-1,white_y-2,limitwhite+1,map,limit);
        }   
        if(map[white_y+1][white_x+2]==0){
            movewhite(white_x+2,white_y+1,limitwhite+1,map,limit);
        }   
        if(map[white_y+1][white_x-2]==0){
            movewhite(white_x-2,white_y+1,limitwhite+1,map,limit);
        }   
        if(map[white_y-1][white_x+2]==0){
            movewhite(white_x+2,white_y-1,limitwhite+1,map,limit);
        }   
        if(map[white_y-1][white_x-2]==0){
            movewhite(white_x-2,white_y-1,limitwhite+1,map,limit);
        }               
    }   
}
int main()
{
    int tc;
    scanf("%d",&tc); // amount of test case
    for(int t=1;t<=tc;t++){
        int limit,map[10][10]={{}};
        scanf("%d",&limit); // amount of limit each horse have
        int limitblack = 0, limitwhite = 0;
        char black[3],white[3];
        int black1,white1;
        int black_x,black_y,white_x,white_y;
        getchar();
        scanf("%s %s",&black,&white); //coordinates ex A1 H8 or G6 B5 
        black_x = black[0] - ('A'-1); // scale 1-8
    //  printf("\n%d\n",black_x);
        black_y = (black[1]-'0');
    //  printf("\n%d\n",black_y);
        white_x = white[0] - ('A'-1); // scale 1-8
        white_y = (white[1]-'0');
//      printf("%d,%d\n",black_x,black_y);
//      printf("%d,%d\n",white_x,white_y);
         //Set Chess board as 0, prevent revisiting in recursion
        for(int i=8;i>=1;i--){
            for(int j=1;j<=8;j++){
                map[i][j] = 0;
            }
        }
        //CHECK
//      for(int i=8;i>=1;i--){
//          for(int j=1;j<=8;j++){
//              if(i==black_x && j==black_y){
//                  printf("B");
//              }
//              else if(i==white_x && j==white_y){
//                  printf("W");
//              } else {
//                  printf("%d",map[i][j]);
//              }
//              
//          }
//          printf("\n");
//      }       
        moveblack(black_x,black_y,limitblack,map,limit);
        movewhite(white_x,white_y,limitwhite,map,limit);

        for(int i=1;i<=8;i++){
            for(int j=1;j<=8;j++){
                if(count[i][j]>=2){
                    counter++;
                }
            }
        }

        if(counter > 0){
            printf("Case #%d: YES\n",t);
        } 
        else if (counter == 0) {
            printf("Case #%d: NO\n",t);
        }
        counter=0;  
    }
    return 0;
}

Answer 1

在进行下一次递归调用时，您没有更新 limit_black limit_white。

moveblack(black_x+1,black_y+2,limitblack,map,limit);
//....

应该是:limitblack+1

moveblack(black_x+1,black_y+2,limitblack+1,map,limit);
// update other calls accordingly.

在基本情况下，您将 limitblack/limitWhite 与 limit 进行比较，这应该可以防止无限递归。

if(limitwhite > limit){
        limitwhite =0;
        return;
}

您也可以在递归开始时移动它。

Can anyone spot the problem or the logic flaw..

是的，您的实现中存在一些逻辑缺陷。首先:您正在使用 count 数组来检查两匹马是否访问了相同的索引。 如果同一个黑马访问该索引两次/多次怎么办。

第二:你的递归没有在下一步中携带确切的访问阶段。您应该传递引用而不是按值传递。

应该是:

void moveblack(int black_x,int black_y,int limitblack,(--> pointer of that map array)int map[10][10],int limit)

此外，索引检查不正确:如果 white_y=1 和 white_x=1

 map[white_y-1][white_x-2]==0

这将产生段错误。

还有其他缺陷。但现在我想这已经足够了。