| 4 | rep(i,0,n) if (cur[i] != 0) h += abs(i - cur[i]); |
| 5 | return h; } |
| 6 | int dfs(int d, int g, int prev) { |
| 7 | int h = calch(); |
| 8 | if (g + h > d) return g + h; |
| 9 | if (h == 0) return 0; |
| 10 | int mn = INF; |
| 11 | rep(di,-2,3) { |
| 12 | if (di == 0) continue; |
| 13 | int nxt = pos + di; |
| 14 | if (nxt == prev) continue; |
| 15 | if (0 <= nxt && nxt < n) { |
| 16 | swap(cur[pos], cur[nxt]); |
| 17 | swap(pos,nxt); |
| 18 | mn = min(mn, dfs(d, g+1, nxt)); |
| 19 | swap(pos,nxt); |
| 20 | swap(cur[pos], cur[nxt]); } |
| 21 | if (mn == 0) break; } |
| 22 | return mn; } |
| 23 | int idastar() { |
| 24 | rep(i,0,n) if (cur[i] == 0) pos = i; |
| 25 | int d = calch(); |