Poj 3050: Hopscotch

poj3050.md

Poj 3050: Hopscotch

題目

分析

將每一個位置當作起點，做一次深度限制為 5 的 dfs，即可跑出所有可能，之後用 set 排除重覆。

AC Code

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int data[5][5];
set<int> ans;

void dfs(int row, int col, int depth, int num) {
    if (depth == 5) {
        ans.insert(num);
        return;
    }

    int dr[4] = {-1, +1, 0, 0};
    int dc[4] = {0, 0, +1, -1};
    for (int i = 0; i < 4; i++) {
        int nr = row + dr[i];
        int nc = col + dc[i];

        if (0 <= nr && nr < 5 && 0 <= nc && nc < 5)
            dfs(nr, nc, depth + 1, num * 10 + data[nr][nc]);
    }
}

int main() {
    ios::sync_with_stdio(false);

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

    for (int row = 0; row < 5; row++)
        for (int col = 0; col < 5; col++)
            dfs(row, col, 0, data[row][col]);

    cout << ans.size() << endl;

    return 0;
}