Codility的一道题

分享一道面试题，求思路！从（0，0）到（A，B），只能走（2，1）或（1，2）向量，就是只能走“日”
求问能否到达以及能到达的话最少需要多少步？

第一题代码：
int searchstep(pair<int,int> dst, queue<int> step, queue<pair<int,int>> position){
    while(!step.empty()){
        int i=position.front().first;
        int j=position.front().second;
        //check curpos
        if(i==dst.first && j==dst.second){
            return step.front();
        }else{
            position.push(make_pair(i+2,j+1));    step.push(step.front()+1);
            position.push(make_pair(i+1,j+2));    step.push(step.front()+1);
            position.push(make_pair(i-1,j+2));    step.push(step.front()+1);
            position.push(make_pair(i-2,j+1));    step.push(step.front()+1);
            position.push(make_pair(i-2,j-1));    step.push(step.front()+1);
. 1point 3 acres            position.push(make_pair(i-1,j-2));    step.push(step.front()+1);
            position.push(make_pair(i+1,j-2));    step.push(step.front()+1);
            position.push(make_pair(i+2,j-1));    step.push(step.front()+1);
            position.pop();    step.pop();
        }
    }
    return -1;
}
int main(int argc, char* argv[]){
    queue<pair<int,int>> pos;
    queue<int> step;
    pos.push(make_pair(0,0));
. 1point3acres.com     step.push(0);
   
    cout<<searchstep(make_pair(0,1),step,pos);
    return 0;
}

bonnachoven 发表于 2016-1-5 13:29
第一题应该bfs或者dfs都可以做吧，感觉bfs会快，因为只用找到最短的一条路径就可以了。
第二题有时间空间 ...

第二题不知为何只有60%的正确率。。。时空都是O（N）吧我记得，感觉没什么问题啊，所以怀疑test case的问题。。。
另外第一题有类似问题代码吗？

bonnachoven 发表于 2016-1-5 13:29
第一题应该bfs或者dfs都可以做吧，感觉bfs会快，因为只用找到最短的一条路径就可以了。
第二题有时间空间 ...

BFS是从中心开始，每个位置衍生出来8个新位置，直到到达终点么？问题的规模是8^k, k是最终步数。有更好的解法吗？

另外还有一道题performance只有60%。
题目是这样的：给定序列A，比如［1，2，3，4，5，1］，给定target number，比如就是1。
要求对序列切一刀，使得左半部分的target number数量等于右半部分不是target number的数量。
大家有什么好算法吗？能提供edge case吗？谢谢！

第一题应该bfs或者dfs都可以做吧，感觉bfs会快，因为只用找到最短的一条路径就可以了。
第二题有时间空间复杂度要求么？没有的话感觉brute force用两个数组分别记左边等于target和右边不等于target的然后再比较对应位置就可以了吧。。。

illuminati 发表于 2016-1-5 13:32
第二题不知为何只有60%的正确率。。。时空都是O（N）吧我记得，感觉没什么问题啊，所以怀疑test case的问 ...

不要怀疑test case，

60%明显就是错的离谱了。

illuminati 发表于 2016-1-5 13:32
第二题不知为何只有60%的正确率。。。时空都是O（N）吧我记得，感觉没什么问题啊，所以怀疑test case的问 ...

继续查bug吧

rayord 发表于 2016-1-6 11:54
.--BFS是从中心开始，每个位置衍生出来8个新位置，直到到达终点么？问题的规模是8^k, k是最终步数。有更好的 ...

......哥，bfs不是这么玩的。

163 发表于 2016-1-6 12:10
......哥，bfs不是这么玩的。

求方法。。