Language: C++

#include <vector>
#include <iostream>
#include <algorithm>  //swap
#include "puzzle.hpp"
using namespace std;

static int ManhattanDistanceTable[kPanelNum][kPanelNum];

int CalcSumManhattanDistance(const Puzzle& pz) {
	int manhattan_distance = 0;
	for (int i = 0; i < kPanelNum; i++) {
		if (pz.board_situation[i] == kPanelNum) {
			continue;
		}
		manhattan_distance += ManhattanDistanceTable[i][pz.board_situation[i] - 1];
	}
	return manhattan_distance;
}
//デバッグ用
void PrintNowBoard(const Puzzle& now_puzzle) {
	cout << "+--+--+--+--+" << endl;
	for (int i = 0; i < kPanelNum; i++) {
		if (now_puzzle.board_situation[i] == kPanelNum) {
			printf("|  ");
		} else {
			printf("|%2d", now_puzzle.board_situation[i]);
		}
		if ((i != 0) && (i % kBoardWidth == 3)) {
			cout << "|" << endl;
			cout << "+--+--+--+--+" << endl;
		}
	}
}

void UpdateBoardInfo(Puzzle* board_current_state, const int y_pos, const int x_pos, const int y_pos_moved, const int x_pos_moved){
	int idx_space_pos_destination = y_pos_moved * kBoardWidth + x_pos_moved;
	int idx_space_pos_current = y_pos * kBoardWidth + x_pos;
	//CalcSumManhattanDistanceでも求められるが、処理速度遅くなる
	board_current_state->sum_ManhattanDistance  -=  ManhattanDistanceTable[idx_space_pos_destination][board_current_state->board_situation[idx_space_pos_destination] - 1];
	board_current_state->sum_ManhattanDistance  += ManhattanDistanceTable[ idx_space_pos_current][board_current_state->board_situation[idx_space_pos_destination] - 1];

	swap(board_current_state->board_situation[idx_space_pos_destination], board_current_state->board_situation[idx_space_pos_current]);
	board_current_state->idx_space_pos = idx_space_pos_destination;
//	board_current_state->sum_ManhattanDistance  = CalcSumManhattanDistance(*board_current_state);
}

/**
 * dfs関数：深さ優先探索
 */
bool DFS(int current_depth, int prev_direction, Puzzle* board_current_state, int depth_limit, vector<int>* route) {
  //デバッグ用
  // static int cnt = 0;
  // cout << cnt++ << "回目" << endl;
  // PrintNowBoard(board_current_state);
  // cout << "SumMD : " << board_current_state.sum_MD << endl << endl;

	if (board_current_state->sum_ManhattanDistance == 0)
		return true;
	//現在の深さ＋下限値(LowerBound)＞今回の深さ制限
	//これ以上先に進んでも無駄
	if (current_depth + board_current_state->sum_ManhattanDistance > depth_limit)
		return false;

	//左上を原点(0,0)としたときの現在の「0」の位置（(y_pos,x_pos)座標）
	int current_space_y_pos = board_current_state->idx_space_pos / kBoardHeight;
	int current_space_x_pos = board_current_state->idx_space_pos % kBoardWidth;

	//右、上、左、下の順にループ
	for (int direction = RIGHT; direction < kDirectionNum; direction++) {
		int y_pos_moved = current_space_y_pos + dx[direction];
		int x_pos_moved = current_space_x_pos + dy[direction];
    //boardの範囲の場合continue
		if( !(0<=y_pos_moved && y_pos_moved<kBoardHeight) || !(0<=x_pos_moved && x_pos_moved<kBoardWidth) ){
			continue;
		}
		//以前通った方角の場合continue
		if (abs(prev_direction - direction) == kAlreadyPassing) {
			continue;
		}
		//探索失敗時に一つ戻るために現在の情報を保存しておく
		Puzzle tmp_board_state = *board_current_state;

		UpdateBoardInfo(board_current_state, current_space_y_pos, current_space_x_pos, y_pos_moved, x_pos_moved);

		//MDの合計値が0（各パネルが正しい位置に整列済み）のときに真
		if (DFS(current_depth + 1, direction, board_current_state, depth_limit, route)) {
			(*route)[current_depth] = direction;
			return true;
		}
		*board_current_state = tmp_board_state;
	}
	return false;
}

string ParseShortestPath(const Puzzle& board_input_state) {
	vector<int> route(kMaxMovementNum,0);
	//説明変数  最短手数
	int  min_movement_num = board_input_state.sum_ManhattanDistance;
	Puzzle state = board_input_state;
	for (int limit = min_movement_num; limit <= kMaxMovementNum; limit++) {
		if (DFS(kDepthBegin, kNotDirection, &state, limit, &route)) {
			string direction_movement = "";
			for (int i = 0; i < limit; i++){
				direction_movement += kDirection[route[i]];
			}
			return direction_movement;
		}
	}
	return "unsolvabe";
}

void InputPuzzleInfo(Puzzle* input_puzzle){
	for (int i = 0; i < kPanelNum; i++) {
		cin >> input_puzzle->board_situation[i];
		if (input_puzzle->board_situation[i] == 0) {
			input_puzzle->board_situation[i] = kPanelNum;
			input_puzzle->idx_space_pos = i;
		}
	}
	//各パネルの最短手数(マンハッタン距離)の合計値
	input_puzzle->sum_ManhattanDistance = CalcSumManhattanDistance(*input_puzzle);
}

void InitializeManhattanDistanceTable(){
	for (int i = 0; i < kPanelNum; i++){
		for (int j = 0; j < kPanelNum; j++){
			ManhattanDistanceTable[i][j] = abs(i / kBoardHeight - j / kBoardHeight) + abs(i % kBoardWidth - j % kBoardWidth);
		}
	}
	//デバッグ用
//	for (int i = 0; i < kPanelNum; i++) {
//		printf("sx = %2d : ", i);
//		for (int j = 0; j < kPanelNum; j++) {
//			cout << MDT[i][j] << " ";
//		}
//		cout << endl;
//	}
}
void Output(const string& direction_movement){
	if(direction_movement == "unsolvabe"){
		cout << direction_movement << endl;
	}
	else{
		//	cout << direction_movement << endl;
		int fewest_steps = direction_movement.size();
		cout << fewest_steps << endl;
	}
}
/*
 *
	1 3 0
	4 2 5
	7 8 6
 *
 * 4
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/*----------       定数定義       ----------*/

#define BOARD_SIZE          3       // パズルの行数（列数）
#define PANEL_NUM           9       // マスの総数
#define MAX_PATTERN         362880  // 考えられるパズルの組み合わせ数 (9の階乗)
#define MOVE_DIRECTION_NUM  4       // 移動方向の数
#define MALLOC_ERR         -1       // メモリ確保失敗
#define SEARCH_FAILURE     -2       // 探索失敗


/*----------      構造体宣言      ----------*/

/*
 *  パズル盤面の情報をもつ構造体
 */
typedef struct {
    int field[PANEL_NUM];  // パズルの配置
    int space_position;     // 空白の位置
    int num_moves;          // 手数
} Puzzle;

/*
 *  キューを実装するための構造体
 */
typedef struct {
    Puzzle *data;
    int head;
    int tail;
} Queue;


/*----------   プロトタイプ宣言   ----------*/

bool InitQueue(Queue *queue);
bool isEmpty(Queue *queue);
void Push(Queue *queue, Puzzle puzzle);
Puzzle Pop(Queue *queue);
int CalcHashValue(int *field);
int BreadthFirstSearch(Puzzle *start);


/*----------      メイン処理      ----------*/

int main() {
    Puzzle start;

    // 初期配置の読み込み
    for(int i = 0; i < PANEL_NUM; i++ ){
        scanf("%d", &start.field[i]);
        if(start.field[i] == 0){
            start.space_position = i;
        }
    }

    int answer = BreadthFirstSearch(&start);

    if(answer == MALLOC_ERR){
        printf("malloc error\n");
    }
    else if(answer == SEARCH_FAILURE){
        printf("探索失敗\n");
    }
    else{
        printf("%d\n", answer);
    }
    return EXIT_SUCCESS;
}


/*----------       関数定義       ----------*/

/*
 *  幅優先探索でパズルの最短手数を求める
 *
 *  戻り値：
 *      探索に成功した場合    最短手数
 *      mallocに失敗した場合 MALLOC_ERR
 *      探索に失敗した場合    SEARCH_FAILURE
 */
int BreadthFirstSearch(Puzzle *start) {
    start->num_moves = 0;

    Queue queue;

    if(!InitQueue(&queue)){
        return MALLOC_ERR;
    }
    Push(&queue, *start);

    bool *hash_table = (bool*) malloc(sizeof(bool) * MAX_PATTERN);  // 一度探索した配置を覚えておくためのテーブル
    if(!hash_table){
        return MALLOC_ERR;
    }

    int goal_field[PANEL_NUM] = {1, 2, 3, 4, 5, 6, 7, 8, 0};   // ゴールの配置
    int goal_hash_value = CalcHashValue(goal_field);           // ゴールのハッシュ値

    hash_table[CalcHashValue(start->field)] = true;

    // 上下左右の空白の移動方向を定義
    const int move_direction_x[MOVE_DIRECTION_NUM] = {-1, 0, 1, 0};
    const int move_direction_y[MOVE_DIRECTION_NUM] = {0, -1, 0, 1};

    while(!isEmpty(&queue)){

        Puzzle now = Pop(&queue); // キューの先頭の盤面を取り出す

        // 現在のハッシュ値とゴールのハッシュ値が一致したら終了
        if(CalcHashValue(now.field) == goal_hash_value){
        	free(queue.data);
        	free(hash_table);
        	return now.num_moves;
        }

        int now_space_pos_x = now.space_position / BOARD_SIZE;
        int now_space_pos_y = now.space_position % BOARD_SIZE;

        // 上下左右の4方向に空白を移動した際の盤面をキューに追加する
        for(int i = 0; i < MOVE_DIRECTION_NUM; i++){
            int moved_space_pos_x = now_space_pos_x + move_direction_x[i];
            int moved_space_pos_y = now_space_pos_y + move_direction_y[i];

            if(moved_space_pos_x < 0 || moved_space_pos_y < 0 || moved_space_pos_x >= BOARD_SIZE || moved_space_pos_y >= BOARD_SIZE){
                continue;  // 移動後の空白の位置がパズルの枠から出ている場合は次へ
            }

            Puzzle next = now; // 空白を移動した際の盤面を作成

            int moved_space_posision = moved_space_pos_x * BOARD_SIZE + moved_space_pos_y;

            // 空白位置の移動
            int temp = next.field[now.space_position];
            next.field[now.space_position] = next.field[moved_space_posision];
            next.field[moved_space_posision] = temp;

            next.space_position = moved_space_posision;

            // 盤面が重複しているかを調べる
            if(!hash_table[CalcHashValue(next.field)]){
            	//重複が無ければハッシュテーブルを更新し、盤面をキューに追加する
                hash_table[CalcHashValue(next.field)] = true;
                next.num_moves++;
                Push(&queue, next);
            }
        }
    }

    // ゴール盤面にたどり着かずに、キューが空になった場合は探索失敗
    free(queue.data);
    free(hash_table);
    return SEARCH_FAILURE;
}

/*
 *  キューを初期化する
 *
 *  戻り値：
 *      初期化に成功すれば true、失敗すれば false
 */
bool InitQueue(Queue *queue) {
    queue->head = 0;
    queue->tail = 0;
    queue->data = (Puzzle*) malloc(sizeof(Puzzle) * MAX_PATTERN);
    if(!queue->data){
        return false;
    }
    return true;
}

/*
 *  キューが空がどうか調べる
 *
 *  戻り値：
 *      空であれば true、そうれなければ false
 */
bool isEmpty(Queue *queue) {
    return queue->head == queue->tail;
}

/*
 *  キューに要素を追加する
 *
 *  戻り値:
 *      なし
 */
void Push(Queue *queue, Puzzle puzzle) {
    queue->data[queue->tail] = puzzle;
    queue->tail = (queue->tail + 1) % MAX_PATTERN;
}

/*
 *  キューの先頭要素を取り出す
 *
 *  戻り値：
 *      キューの先頭要素のパズル
 */
Puzzle Pop(Queue *queue) {
    Puzzle puzzle = queue->data[queue->head];
    queue->head = (queue->head + 1) % MAX_PATTERN;
    return puzzle;
}

/*
 *  パズル盤面のハッシュ値を計算する
 *
 *  戻り値：
 *      盤面のハッシュ値
 */
//int CalcHashValue(int *field) {
//    int res = 0;
//    for(int i = 0, fac = 1; i < PANEL_NUM; fac *= ++i){
//        int count = 0;
//        for(int j = 0; j < i; j++){
//            if(field[j] < field[i]){
//                count++;
//            }
//        }
//        res += count * fac;
//    }
//    return res;
//}


int CalcHashValue(int *field) {
	puts("");
	int res = 0;
	for(int i = 0, fac = 1; i < PANEL_NUM; fac *= ++i){
		printf("fac : %d ",fac);
		int count = 0;
		for(int j = 0; j < i; j++){
			if(field[j] < field[i]){
				count++;
			}
		}
		res += count * fac;
		printf("cnt : %d  res : %d  ", count, res);
		puts("");
	}
	return res;
}

//////////////////////////////////////////////
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;

constexpr int BOARD_SIZE = 3, PANEL_NUM = 9;

struct Puzzle {
    int field[PANEL_NUM];
    int space_position;
    string path;

    bool operator<(const Puzzle& puzzle) const {
        for(int i = 0; i < PANEL_NUM; ++i){
            if(field[i] == puzzle.field[i]){
                continue;
            }
            return field[i] > puzzle.field[i];
        }
        return false;
    }
};

/**
 *  位置があっているかどうか判定する
 */
bool isTarget(const Puzzle& puzzle){
    for(int i = 0; i < PANEL_NUM; ++i){
        if(puzzle.field[i] != i+1){
            return false;
        }
    }
    return true;
}

/**
 *  幅優先探索
 */
string bfs(const Puzzle& origin){
    queue<Puzzle> que;
    map<Puzzle, bool> mp;    // 配置を記録していく
    que.push(origin);
    mp[origin] = true;

    constexpr int dx[] = {-1, 0, 1, 0};
    constexpr int dy[] = {0, -1, 0, 1};
    constexpr char direction[] = {'u', 'l', 'd', 'r'};
                                 // up, left, down, right
    while(!que.empty()){
        Puzzle parent = que.front();
        que.pop();
        if(isTarget(parent)){    // もしパズルuがターゲットと合致していれば終わり
            return parent.path;
        }
        int sx = parent.space_position / BOARD_SIZE;   // space x
        int sy = parent.space_position % BOARD_SIZE;   // space y

        for(int i = 0; i < 4; ++i){
            int tx = sx + dx[i];    // transfer x
            int ty = sy + dy[i];    // transfer y
            if(tx < 0 || ty < 0 || tx >= BOARD_SIZE || ty >= BOARD_SIZE){
                continue;    // 移動先がパズルの枠を超えてしまわないようにする
            }

            Puzzle child = parent;
            swap(child.field[parent.space_position], child.field[tx * BOARD_SIZE + ty]);
            child.space_position = tx * BOARD_SIZE + ty;    // spaceの位置も移動

            if(!mp[child]){    // 既に同じ配置のパズルを動かし済みの場合はスルーする
                mp[child] = true;
                child.path += direction[i];
                que.push(child);
            }
        }
    }
    return "unsolvable";
}


int main(){

    Puzzle puzzle;

    for(int i = 0; i < PANEL_NUM; ++i){
        cin >> puzzle.field[i];
        if(puzzle.field[i] == 0){
            // spaceの場所をセットする
            puzzle.field[i] = PANEL_NUM;
            puzzle.space_position = i;
        }
    }
    puzzle.path = "";

    string ans = bfs(puzzle);
    if(ans != "unsolvable"){
    	cout << ans.size() << endl;
    }

    return 0;
}


Compiler output:
a.cc:4:10: fatal error: puzzle.hpp: No such file or directory
    4 | #include "puzzle.hpp"
      |          ^~~~~~~~~~~~
compilation terminated.