글 읽기 - DSLR 왜 틀렸는지 모르겠어요..

algoshipda 8년 전 0

많아봤자 10000개니깐 그냥 BFS 해서 찾는건데요 오답이 뜨네요.

어디가 잘못됐을까요?

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;

vector<int> visited;
char op[10005];
int parent[10005];
int A,B;
int w[] = {0,1,10,100,1000};
int name[] = {'D','S','L','R'};

int doubleup(int x)
{
    return (x*2)%10000;
}
int left(int x)
{
    if(x==0)return 0;
    int cnt = 0;
    int tmp = x;
    while(tmp){
        cnt++;
        tmp/=10;
    }
    int first = x / w[cnt];
    int last = x % w[cnt];
    return (last)*10 + first;
}

int right(int x)
{
    if(x==0)return 0;
    int cnt = 0;
    int tmp = x;
    while(tmp){
        cnt++;
        tmp/=10;
    }
    int last = x%10;
    return x/10 + last*w[cnt];
}

int sub(int x)
{
    return (x+9999)%10000;
}

void bfs()
{
    visited = vector<int>(10005,0);
    queue<int> q;
    q.push(A);
    visited[A] = 1;
    int tmp[4];
    while(q.front()!=B && !q.empty()){
        int cur = q.front();q.pop();
        tmp[0] = doubleup(cur);
        tmp[1] = sub(cur);
        tmp[2] = left(cur);
        tmp[3] = right(cur);
        for(int i=0;i<4;++i){
            if(!visited[tmp[i]]){
                q.push(tmp[i]);
                visited[tmp[i]] = 1;
                op[tmp[i]] = name[i];
                parent[tmp[i]] = cur;
            }
        }
    }
}

int main()
{
    int t;
    for(scanf("%d",&t);t;--t){
        memset(parent,0,sizeof(parent));
        memset(op,0,sizeof(op));
        scanf("%d%d",&A,&B);
        bfs();
        string s;
        while(A!=B){
            s.push_back(op[B]);
            B=parent[B];
        }
        reverse(s.begin(),s.end());
        printf("%s\n",s.c_str());
    }
}

baekjoon 8년 전 0

1 9 같은 경우를 잘 처리하지 못하네요.

algoshipda 8년 전 1

@baekjoon 아 1을 L , R 하면 그대로 1이 아니라 10 1000이 돼는거였네요 감사합니다

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

문제

문제

출처

ICPC

DSLR 왜 틀렸는지 모르겠어요..

algoshipda 8년 전 0

baekjoon 8년 전 0

algoshipda 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말