Curling 2.0(dfs)

The movement of the stone obeys the following rules:

• At the beginning, the stone stands still at the start square.
• The movements of the stone are restricted to x and y directions. Diagonal moves are prohibited.
• When the stone stands still, you can make it moving by throwing it. You may throw it to any direction unless it is blocked immediately(Fig. 2(a)).
• Once thrown, the stone keeps moving to the same direction until one of the following occurs:You cannot throw the stone more than 10 times in a game. If the stone does not reach the goal in 10 moves, the game ends in failure.
  • The stone hits a block (Fig. 2(b), (c)).
    • The stone stops at the square next to the block it hit.
    • The block disappears.
  • The stone gets out of the board.
    • The game ends in failure.
  • The stone reaches the goal square.
    • The stone stops there and the game ends in success.

which means小球每次只能在一个方向滑动，直到他撞墙（墙会消失），如果小球滑出了界外，就不继续考虑这个方向，从小球滑之前的位置遍历别的方向

#include <iostream>
#define maxn 401
using namespace std;
int w, h, min;
int cell[maxn][maxn];
const int INF= 9999999;
struct direction{//方向数组
    int r, c;
}dir[4] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
bool check(int nowh, int noww)//出界，fail
{
    if (nowh < 0 || noww < 0 || nowh >= h || noww >= w){
        return false;
    }
    return true;
}
void dfs(int nowi, int nowj, int step){
    step++;//attention!!!每次进入搜索步数都要++
    if (step > 10){//搜索超过10次就输了
        return;//返回主函数
    }
    for (int i = 0; i < 4; i++){
        int nexti = dir[i].r + nowi;
        int nextj = dir[i].c + nowj;
        int flag = 0;//flag放在这里惹
        if (cell[nexti][nextj] == 1||check(nexti,nextj)==false){//是墙或者越界的地方不用进行搜索
            continue;
        }
        //以下是搜索
        while (cell[nexti][nextj] != 1 && cell[nexti][nextj] != 3){
            nexti += dir[i].r;
            nextj += dir[i].c;
            if (check(nexti, nextj) == false){//越界了
                flag = 1;
                break;
            }
        }
        if (flag){//此方向不可走
            continue;
        }
        if (cell[nexti][nextj] == 3){
            if (step < min){
                min = step;
            }
            continue;//继续寻找别的路径
        }
        //cell是0或2，因为起点没改为0
        cell[nexti][nextj] = 0;
        dfs(nexti - dir[i].r, nextj - dir[i].c, step);//坑爹，步数在这里加1就错
        cell[nexti][nextj] = 1;
    }
}
int main()
{
#ifdef local
    freopen("input.txt", "r", stdin);
#endif // local

    int si, sj;
    while (cin >> w >> h&&w != 0 && h != 0){
        for (int i = 0; i < h; i++){
            for (int j = 0; j < w; j++){
                cin >> cell[i][j];
                if (cell[i][j] == 2){
                    si = i;
                    sj = j;
                }
            }
        }
        min = INF;
        dfs(si, sj, 0);
        if (min != INF){
            cout << min << endl;
        }
        else{
            cout << -1 << endl;
        }
    }
    return 0;
}

以上