競プロはじめました

競プロ初心者のブログ

AOJ0121

AOJ0121

7 パズル | Aizu Online Judge

幅優先探索の練習です。

入出力のところで戸惑いました。 iostreamを使わなきゃいけないんですかね。。。?

今回は方針が全然立ちませんでした。 最初、それぞれのデータセットに対して毎回計算させてました。 最初に計算して、与えられたセットに対して値を返すmapを作成すればいいんですね。。。

拘束条件も正確ではなくて闇を見ました。 問題をわかりやすくするために文字列として扱ったのはいいものの、問題の状況を完全に見落としてました。

いろいろ苦難して解答時間は三時間です

以下、コードです

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

string data;
char goal[9] = "01234567";
queue<string> qu;
map<string,int> mp;
int d[4] = {-4,-1,1,4};
int pos;
int ans[1000];
char tmp;


void solve(){
  mp[goal] = 0;
  qu.push(goal);
  string pre_data;
  while(qu.size()){
    data = qu.front();
    pre_data = data;
    qu.pop();
    pos = data.find('0');
    for(int i = 0; i < 4; i++){
      if(pos + d[i] >= 0 && pos + d[i] < 8 && !(pos == 3 && d[i] == 1) && !(pos == 4 && d[i] == -1)){
        data = pre_data;
        swap(data[pos],data[pos+d[i]]);
        if(mp.find(data) == mp.end()){
          mp[data] = mp[pre_data] + 1;
          qu.push(data);
        }
      }
    }
  }
}

int main(){
  int n = 0;
  size_t c;
  solve();
  while(getline(cin, data)){
    while((c = data.find_first_of(" ")) != string::npos){
      data.erase(c,1);
    }
    ans[n++] = mp[data];
  }
  for(int i = 0; i < n; i++)
    printf("%d\n", ans[i]);
}