topcoder SRM 628 DIV2 BishopMove

时间：2020-12-11 08:30:17

题目比较简单。

注意看测试用例2，给的提示

Please note that this is the largest possible return value: whenever there is a solution, there is a solution that uses at most two moves.

最多只有两步

#include <vector>

#include <string>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <cstring>

#include <climits>

#include <queue>

using namespace std;

class BishopMove

{

public:

    typedef pair<int,int> Point;

    int howManyMoves(int r1, int c1, int r2, int c2)

    {

        queue<Point> que;

        que.push(Point(r1,c1));

        int step = ;

        bool visit[][];

        memset(visit,false,sizeof(visit));

        int dx[]={,-,,-};

        int dy[]={,,-,-};

        while(!que.empty()){

            int cnt = que.size();

            while(cnt-->){

                Point tmp = que.front();que.pop();

                visit[tmp.first][tmp.second] = true;

                if(tmp.first == r2 && tmp.second == c2) return step;

                for(int k = ; k <  ; ++ k){

                    for(int i =  ; i  < ; ++ i){

                        int x = tmp.first+dx[i]*k,y=tmp.second+dy[i]*k;

                        if(x>= && x <  && y>= && y< && !visit[x][y]) que.push(Point(x,y));

                    }

                }

            }

            step++;

        }

        return -;

    }

};

// Powered by FileEdit

// Powered by TZTester 1.01 [25-Feb-2003]

// Powered by CodeProcessor

BFS解法

#include <vector>

#include <string>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <cstring>

#include <climits>

#include <queue>

using namespace std;

class BishopMove

{

public:

    typedef pair<int,int> Point;

    bool visit[][];

    Point start,endp;

    int res;

    const int dx[]={,-,,-};

    const int dy[]={,,-, };

    void dfs(Point pos,int step){

        if(pos.first == endp.first && pos.second == endp.second){

            res=min(res,step);

            return;

        }

        if(step > res) return;

        for(int k =  ; k < ; ++ k){

            for(int i =  ; i < ; ++ i){

                int x = pos.first+k*dx[i], y =pos.second+k*dy[i];

                if(x>= && x<  && y>= && y <  && !visit[x][y]){

                    visit[x][y] = true;

                    dfs(Point(x,y),step+);

                    visit[x][y] = false;

                }

            }

        }

    }

    int howManyMoves(int r1, int c1, int r2, int c2)

    {

        memset(visit,false,sizeof(visit));

        start.first = r1;start.second =c1;

        endp.first = r2; endp.second = c2;

        res = ;

        visit[r1][c1] = true;

        dfs(start,);

        if(res == ) res=-;

        return res;

    }

// BEGIN CUT HERE

    public:

    void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); }

    private:

    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

    void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

    void test_case_0() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; verify_case(, Arg4, howManyMoves(Arg0, Arg1, Arg2, Arg3)); }

    void test_case_1() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; verify_case(, Arg4, howManyMoves(Arg0, Arg1, Arg2, Arg3)); }

    void test_case_2() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = ; verify_case(, Arg4, howManyMoves(Arg0, Arg1, Arg2, Arg3)); }

    void test_case_3() { int Arg0 = ; int Arg1 = ; int Arg2 = ; int Arg3 = ; int Arg4 = -; verify_case(, Arg4, howManyMoves(Arg0, Arg1, Arg2, Arg3)); }

// END CUT HERE

};

// BEGIN CUT HERE

int main()

{

    BishopMove ___test;

    ___test.run_test(-);

}

// END CUT HERE

DFS解法

由于题目最多是两步，故结果只能是-1，0，1，2

当两个位置的奇偶性不同时，结果是-1，

当两个位置相等时是0

当abs(c) 与abs(r)相等的视乎，结果是1

其他结果是2

#include <vector>

#include <string>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <cstring>

#include <climits>

#include <queue>

using namespace std;

class BishopMove

{

public:

    int howManyMoves(int r1, int c1, int r2, int c2)

    {

        if(((r1+c1)%) ^ ((r2+c2)%) ) return -;

        if(r1==r2 && c1 == c2 ) return ;

        if(abs(r2-r1) == abs(c2-c1)) return ;

        return ;

    }

};

// Powered by FileEdit

// Powered by TZTester 1.01 [25-Feb-2003]

// Powered by CodeProcessor

相关文章