首页 > > 程序设计 > C/C++ >

Curling 2.0(dfs)

2018-06-17 20:30:20来源：未知阅读 ()

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;
}