这道题目由于每走一步的时候毛毛球是可以变换的 换言之 主体不唯一 所以这里搜索的设计有变化

再就是几个回溯的过程要注意。，。  小心使得万年船

#include <iostream>#include <cstdio>using namespace std;char map[10][10];int num;int flag;int mmove;int dir[4][2] = {{-1,0},{0,-1},{0,1},{1,0}}; //U、L、R、Dchar tow[4] = {‘U‘,‘L‘,‘R‘,‘D‘};struct node{    int x,y;    int direction;}path[15];int is_in(int x, int y) //判断是否在游戏界面中{    if(x >= 0 && x <= 6 && y >= 0 && y <= 7)        return 1;    else        return 0;}void dfs(int cur){    if(cur == num)    {    //走了num-1步之后直接返回    /*      没成功走一次，都会把一个毛毛球推出游戏界面，所以最多只可能走num-1步    */        flag = 1; //已经走完了相应的步数        return;    }    for(int i=0; i<=6; i++)    {        for(int j=0; j<=7; j++)        {            if(map[i][j] == ‘O‘) //按顺序进行搜索，如果搜索到了一个毛毛球，就看它是否能够移动            {                mmove = 0;                for(int d=0; d<4; d++)                {                    int nx = i + dir[d][0];                    int ny = j + dir[d][1];                    if(is_in(nx, ny) && map[nx][ny] == ‘O‘) //前方有毛毛球阻碍无法移动，直接continue选取下一个方向                        continue;                    /*                    while循环这部分处理是关键，这里主要要处理好手拨动的毛毛球遇到另外一个球时要处理的状况，以及                    撞击力量的传递处理。                    */                    while(is_in(nx, ny))                    {                        nx += dir[d][0];                        ny += dir[d][1];                         /*    遇到毛毛球k，其前面那个必然要为‘O‘，而这个毛毛球k必须变为‘X‘。                             通过while循环就可以处理好遇到毛毛球的情况，并且处理好撞击传递                            的情况，例如第二组数据的撞击传递，所以这里设计的还是很巧妙的。                          */                        if(map[nx][ny] == ‘O‘)                        {                            mmove = 1; //手拨动的毛毛球map[i][j]是可以移动的                            map[nx][ny] = ‘X‘;                            map[nx - dir[d][0]][ny - dir[d][1]] = ‘O‘;                        }                    }                    if(mmove) //可以移动，进行记录                    {                        map[i][j] = ‘X‘; //移动之后原来的位置当然要置为‘X‘                        path[cur].x = i;                        path[cur].y = j;                        path[cur].direction = d;                        dfs(cur + 1);                        //回溯之后                        if(flag == 1)  //已经走完了就应该直接返回                             return;                                  //反方向走                        nx -= dir[d][0];                        ny -= dir[d][1];                        while(nx != i || ny != j) //一直会推到手拨动球的起点map[i][j]                        {                            if(map[nx][ny] == ‘O‘)  /*这说明是前面的球移动到此处的一个位置，                                                     所以该位置还原成‘X‘，而它后面的那个位置应该                                                     还原成‘O‘                                                     */                            {                                map[nx][ny] = ‘X‘;                                map[nx + dir[d][0]][ny + dir[d][1]] = ‘O‘;                            }                            nx -= dir[d][0];                            ny -= dir[d][1];                        }                        map[i][j] = ‘O‘; //起点还原                    }                }            }        }    }}int main(){    int kase = 1;    while(scanf("%s",map[0]) != EOF)    {        num = flag = 0;        for(int i=1; i<=6; i++)        {            scanf("%s",map[i]);        }        for(int i=0; i<=6; i++)        {            for(int j=0; j<=7; j++)            {                if(map[i][j] == ‘O‘)                {                    num++; //记录毛毛球的个数                }            }        }        dfs(1);        if(kase != 1)            cout<<endl;        cout<<"CASE #"<<kase++<<":"<<endl;        for(int i = 1; i<=num-1; i++)        {            cout<<path[i].x<<" "<<path[i].y<<" "<<tow[path[i].direction]<<endl;        }    }    return 0;}

hdu 3500 还是搜索