Language: C++

// ALDS1_13_C.cpp
// Heuristic Search - 15 Puzzle

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int N = 4;
const int N2 = 16;
const int INF = 50;
struct Puzzle {
    int f[N2];
    //int space;
    string path;

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

static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};
static const char dir[4] = {'u', 'l', 'd', 'r'};
map<Puzzle, bool> ms;
Puzzle in;
int ministep = INF;
int sx = 0;
int sy = 0;

void swap(int& a, int& b)
{
    int t = a;
    a = b;
    b = t;
}

bool isTarget(Puzzle p)
{
    for (int i = 0; i < N2; i++) {
        if (p.f[i] != i + 1)
            return false;
    }
    return true;
}

int getAllMD(Puzzle p)
{
    int dist = 0;
    int x, y;
    int ux, uy;
    for (int i = 0; i < N2; i++) {
        if (p.f[i] == N2) continue; // ??????0??????
        x = (p.f[i] - 1) / N;
        y = (p.f[i] - 1) % N;
        ux = i / N;
        uy = i % N;
        dist += abs(x - ux) + abs(y - uy);
    }
    return dist;
}

bool bfs(int i)
{
    if (isTarget(in)) {
        ministep = min(ministep, i);
//        cout << "ministep = " << ministep << endl;
        return true;
    }
    if (ms[in] || limit < i + getAllMD(in)) {
        return false;
    }
    
    ms[in] = true;
    for (int u = 0; u < 4; u++) {
        int tx = sx + dx[u];
        int ty = sy + dy[u];
        if (tx < 0 || tx >= N || ty < 0 || ty >= N)
            continue;
        swap(in.f[sx * N + sy], in.f[tx * N + ty]);
        sx = tx;
        sy = ty;
        in.path += dir[u];
        /* test */
//    cout << "(i = " << i << ") " << in.path << endl;
//    for (int j = 0; j < N2; j++)
//        cout << " " << in.f[j];
//    cout << endl;
//    cout << "MD: " << getAllMD(in) << endl;
        bfs(i+1);
        sx = sx - dx[u];
        sy = sy - dy[u];
        swap(in.f[sx * N + sy], in.f[tx * N + ty]);
        in.path.pop_back();
    }
    ms[in] = false;
	return false;
}

void iterative_deepening()
{
	for (limit = getAllMD(in); limit <= INF; limit++) {
		if (bfs(0)) {
			return in.path;
		}
	}
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    for (int i = 0; i < N2; i++) {
        cin >> in.f[i];
        if (in.f[i] == 0) {
            sx = i / N;
            sy = i % N;
            in.f[i] = N2; // ??????isTarget?????????
        }
    }
    string ans = iterative_deepening();
	cout << ans.size() << endl;
    return 0;
}

Compiler output:
a.cc: In function 'bool bfs(int)':
a.cc:75:19: error: 'limit' was not declared in this scope
   75 |     if (ms[in] || limit < i + getAllMD(in)) {
      |                   ^~~~~
a.cc: In function 'void iterative_deepening()':
a.cc:107:14: error: 'limit' was not declared in this scope
  107 |         for (limit = getAllMD(in); limit <= INF; limit++) {
      |              ^~~~~
a.cc:109:35: error: return-statement with a value, in function returning 'void' [-fpermissive]
  109 |                         return in.path;
      |                                ~~~^~~~
a.cc: In function 'int main()':
a.cc:127:37: error: conversion from 'void' to non-scalar type 'std::string' {aka 'std::__cxx11::basic_string<char>'} requested
  127 |     string ans = iterative_deepening();
      |                  ~~~~~~~~~~~~~~~~~~~^~