3050 Hopscotch

3050 Hopscotch

概要

５×５のマスに整数が書いてある。

適当なマスからスタートして４方好きな方向に５回移動する。

そのとき到達した６個のマスを順に並べてできる数は

何個あるか答える。

例えば、1→1→1→1→2→1と移動したら111121が得られる。

方針

(4^5)*5*5だから全部やっても大丈夫な気がしたけどTLEもらったので、

メモ化探索してみる。

set dfs(int r, int c, int ith)でr行c列からithステップの移動でできる数のセットを返す。
何度か同じ引数でdfs(r, c, ith)を呼び出すことになるので、返り値はmemo[r][c][ith]にとっておいて、計算済みならばmemoの値を返す。

最初vectorにしていたけど、setの方が少し速くなった(532MS→469MS)

#include<cstdio>
#include<set>
#include<string>
#include<stdlib.h>
#include<sstream>

using namespace std;

int grid[5][5];
set<string> memo[5][5][7];

int dr[4] = {0, -1, 0, 1};
int dc[4] = {1, 0, -1, 0};

bool valid(int r, int c) {
    return r >= 0 && r < 5 && c >= 0 && c < 5;
}

set<string> dfs(int r, int c, int ith) {
    if (!memo[r][c][ith].empty()) {  // 探索済みならmemoを返す
        return memo[r][c][ith];
    }
    set<string> ret;
    stringstream ss;
    ss << grid[r][c];
    string str;
    ss >> str;
    if (ith == 1) {  // ラストのマス。自分自身を返す
        ret.insert(str);
    } else {
        for (int i = 0; i < 4; ++i) {
            if (valid(r+dr[i], c+dc[i])) {
                set<string> tmp = dfs(r+dr[i], c+dc[i], ith-1);
                set<string>::iterator it = tmp.begin();
                while (it != tmp.end()) {
                    ret.insert(str+*it);
                    ++it;
                } 
            }
        }
    }
    return memo[r][c][ith] = ret;
}

int main() {
    int d;
    for (int r = 0; r < 5; ++r) {
        for (int c = 0; c < 5; ++c) {
            scanf("%d", &grid[r][c]);
        }
    }
    
    set<int> ans;
    for (int r = 0; r < 5; ++r) {
        for (int c = 0; c < 5; ++c) {
            set<string> ret = dfs(r, c, 6); // (r, c)から６マスで得られる数セット
            set<string>::iterator it = ret.begin();
            while (it != ret.end()) {
                ans.insert(atoi((*it).c_str()));
                ++it;
            } 
        }
    }
    printf("%d\n", ans.size());
}

スーパー遅いんですけど(^^;
id:ororog, id:halwhite教えて！