PKU : 3050 - Hopscotch

問題概要

http://poj.org/problem?id=3050
５＊５の数字が書かれたテーブルが与えられます.(数字はおそらく0〜9の1ケタ)
適当な位置から上下左右に移動して6ケタの数字を作るとき, 何種類の数字を作ることができるでしょう.

アルゴリズム

開始位置だけ決めて, そこから全探索で解けると思います.
DFSで実装しました.
O(5 * 5 * 4^6 * 重複をはぶくためのデータ構造のオーダ)

重複をはぶくためのデータ構造は, セットを使うといいと思います.
トライでやってみたら, タイムは半分ぐらい縮みました.

プログラム

string t[5][5];
set<string> ans;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

void solve(int x,int y,int rem,string s){
  if(rem == 0){
    ans.insert(s);
    return;
  }

  rep(i,4){
    int nx = x + dx[i];
    int ny = y + dy[i];

    if(0 <= nx && nx < 5 && 0 <= ny && ny < 5){
      solve(nx,ny,rem-1,s+t[ny][nx]);
    }
  }
}

int main(void){
  rep(i,5){
    rep(j,5){
      cin>>t[i][j];
    }
  }
  rep(i,5){
    rep(j,5){
      solve(j,i,5,t[i][j]);
    }
  }
  cout<<ans.size()<<endl;
}