POJ3050(DFS)

一定要根据数据规模想问题，这题数据规模就不大，时间复杂度大概是O(R*C*dir^step) = O(5*5*4^6)。规模不大，可以无脑DFS,还是这句话，先将简单的写出来再说。

//#define LOCAL

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define SIZE 5

using namespace std;

int map[SIZE][SIZE];
set<int> path;
int dir[][2] = {0, 1, 0, -1, 1, 0, -1, 0};

void dfs(int x, int y, int sub_path, int step){
    if(step == SIZE){
        //printf("sub_path:%d\n", sub_path);
        path.insert(sub_path);
        return;
    }   

    for(int i = 0; i < 4; i++){
        int newx = x + dir[i][0];
        int newy = y + dir[i][1];

        if(0 <= newx && newx < SIZE && 
            0 <= newy && newy < SIZE){
            dfs(newx, newy, sub_path * 10 + map[newx][newy], 
            step + 1);
        }
    }
}

int main(void){
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif

    for(int i = 0; i < SIZE; i++)
    for(int j = 0; j < SIZE; j++)
        scanf("%d", &map[i][j]);

    for(int i = 0; i < SIZE; i++)
    for(int j = 0; j < SIZE; j++)
        dfs(i, j, map[i][j], 0);

    printf("%d\n", (int)path.size());

    return 0;
}