题目比较简单。
注意看测试用例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