poj3009

poj3009.md

Poj 2431

題目

分析

從測資中可以發現，當 stone 撞上 block 後，block 會立即消失，stone 停在 block 的前一格。

因題目有限制搜尋深度，並且為了每次遞迴不記憶整個 board，所以使用 dfs + 剪枝。在每個轉折點依 上下左右 四個方向遞迴搜尋下去（注意，只有當該方向的第一格是空的時才可遞迴該方向），每次遇到 goal，更新 result 值。

AC Code

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

int data[20][20];
int W, H;
int result;

int goal_row;
int goal_col;

int source_row;
int source_col;

int delta_row[4] = {0, 0, +1, -1};
int delta_col[4] = {+1, -1, 0, 0};

bool is_inside(int row, int col) {
    return (0 <= row && row < H && 0 <= col && col < W);
}

void dfs(int row, int col, int depth) {
    // printf("(%d, %d, %d)\n", row, col, depth);

    if (depth > 10)
        return;

    if (depth > result)
        return;

    for (int dir = 0; dir < 4; dir++) {
        int new_row = row + delta_row[dir];
        int new_col = col + delta_col[dir];

        if (is_inside(new_row, new_col) == false || data[new_row][new_col] == 1)
            continue;

        while (is_inside(new_row, new_col) && data[new_row][new_col] == 0) {
            if (new_row == goal_row && new_col == goal_col) {
                result = min(result, depth+1);
                break;
            }

            new_row += delta_row[dir];
            new_col += delta_col[dir];
        }

        if (is_inside(new_row, new_col) == false) {
            continue;
        }
        else if (data[new_row][new_col] == 1) { // encounter blocks
            data[new_row][new_col] = 0;

            int stop_row = new_row - delta_row[dir];
            int stop_col = new_col - delta_col[dir];
            dfs(stop_row, stop_col, depth+1);

            data[new_row][new_col] = 1;
        }
    }
}

int main() {
    while (cin >> W >> H) {
        if (W == 0 && H == 0) break;

        memset(data, -1, sizeof(data));
        result = 11;

        for (int row = 0; row < H; row++) {
            for (int col = 0; col < W; col++) {
                cin >> data[row][col];

                if (data[row][col] == 2) {
                    source_row = row;
                    source_col = col;
                    data[row][col] = 0;
                }

                if (data[row][col] == 3) {
                    goal_row = row;
                    goal_col = col;
                    data[row][col] = 0;
                }
            }
        }

        dfs(source_row, source_col, 0);
        cout << ((result == 11) ? -1 : result) << "\n";
    }

    return 0;
}