POJ 3050 Hopscotch

解法：全探索(dfs)

やるだけである。思ったより簡単で腰を抜かす。

#include <set>
#include <iostream>
#include <cstdio>

using namespace std;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
set<int> tmp;
int ans = 0;
int d[6][6];
void dfs(int x,int y,int s,int g){
  if(s == 6){
    set<int>::iterator it = tmp.find(g);
    if(it == tmp.end()){
      ans++;
      tmp.insert(g);
    }
  }else{
    for(int i = 0;i < 4;i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      
      if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5){
	dfs(nx,ny,s + 1,g*10+d[nx][ny]);
      }
    }
  }
}

int main(){

  for(int i = 0;i < 5;i++){
    for(int j = 0;j < 5;j++){
      scanf("%d",&d[i][j]);
    }
  }
  
  for(int i = 0;i < 5;i++){
    for(int j = 0;j < 5;j++){
      dfs(i,j,1,d[i][j]);
    }
  }
  
  cout << ans << endl;
  
  return 0;

}