글 읽기 - 정말 간단한 알고리즘인데..알고리즘 지적 부탁드립니다.

temp 7년 전 0

점검해본결과

1 3 5
7 2 4
6 8 0

이경우에서 제 닶은 14

정답자들의 답은 18이더군요.

근데 알고리즘이 매우 간단한데..틀릴게없을거같은데 무엇이 문제일까요?

#include<iostream>
#include<queue>
#include<map>
#include<stdio.h>
#include<math.h>
using namespace std;
int cswp[9][4] = { {2, 4}, {1, 3, 5}, {2, 6}, 
                    {1, 5, 7}, {2, 4, 6, 8}, {3, 5, 9},
                    {4, 8}, {5, 7, 9}, {6, 8} };
int main()
{
    int start=0, n, ans=0, end=0;
    for (int i = 0; i < 9; i++)
    {
        cin >> n;
        start = start * 10 + n;
    }
    map<int, int> m;
    queue<int> q;
    q.push(start);
 
    while (!q.empty())
    {
        int SZ = q.size();
        while (SZ--)
        {
            int state = q.front();
            q.pop();
 
            if (state == 123456780)
            {
                end = 1;
                goto end;
            }
            if (m[state]) continue;
            else m[state]++;
 
            char now[13] = { 0, };
            sprintf(now, "%9d", state);
            if (now[0] == ' ') now[0] = '0';
            int idx;
            for (idx = 0; now[idx]; idx++) if (now[idx] == '0') break;
 
            for (int i = 0; cswp[idx][i]; i++)
            {
                swap(now[idx], now[cswp[idx][i] - 1]);
                q.push(atoi(now));
                swap(now[idx], now[cswp[idx][i] - 1]);
            }
        }
        ans++;
    }
end:
    if (end) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

정말 간단한 알고리즘인데..알고리즘 지적 부탁드립니다.

temp 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말