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[][] = {, , , -, , , -, };

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 = ; i < ; i++){
        int newx = x + dir[i][];
        int newy = y + dir[i][];

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

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

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

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

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

    return ;
}