250-point problem
Problem Statement
Janusz is learning how to play chess. He is using the standard chessboard with 8 rows and 8 columns. Both the rows and the columns are numbered 0 through 7. Thus, we can describe each cell using its two coordinates: (row, column).
Janusz recently learned about one of the chess pieces: the bishop. The bishop is a piece that moves diagonally by an arbitrary number of cells. Formally, if a bishop is currently on the cell (r,c) of an empty chessboard, the set of all cells reachable in a single move contains the following cells:
All cells of the form (r+k,c+k), where k is a positive integer.
All cells of the form (r+k,c-k), where k is a positive integer.
All cells of the form (r-k,c+k), where k is a positive integer.
All cells of the form (r-k,c-k), where k is a positive integer.
(Of course, the bishop‘s destination must always be a valid cell on the chessboard.)
Janusz took an empty chessboard and he placed a single bishop onto the cell (r1,c1). He now wants to move it to the cell (r2,c2) using as few moves as possible.
You are given the ints r1, c1, r2, and c2. Compute and return the smallest number of moves a bishop needs to get from (r1,c1) to (r2,c2). If it is impossible for a bishop to reach the target cell, return -1 instead.
Definition
Class:
BishopMove
Method:
howManyMoves
Parameters:
int, int, int, int
Returns:
int
Method signature:
int howManyMoves(int r1, int c1, int r2, int c2)
(be sure your method is public)
Limits
Time limit (s):
2.000
Memory limit (MB):
256
Constraints
-
r1,c1,r2,c2 will be between 0 and 7, inclusive.
Examples
0)
4
6
7
3
Returns: 1
The bishop can go from (4,6) to (7,3) in a single move.
1)
2
5
2
5
Returns: 0
The bishop is already where it should be, no moves are necessary.
2)
1
3
5
5
Returns: 2
In the first move Janusz can move the bishop to the cell (4,6). 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.
3)
4
6
7
4
Returns: -1
If the bishop starts at (4,6), it can never reach (7,4).
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
题意：国际象棋中的象从棋盘位置（r1,c1）到（r2,c2）最少需要几步？不能达到返回-1.
解题：双向宽搜.
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef pair<int,int> P; 5 queue<P>Q1,Q2; 6 int M[2][20][20]; 7 const int Dr[] = {-1,-1,+1,+1}; 8 const int Dc[] = {-1,+1,+1,-1}; 9 class BishopMove{ 10 public: 11 inline bool valid(int x) 12 { 13 return 0 <= x && x <= 7; 14 } 15 int walk(int who,int r,int c,int v) 16 { 17 int k,d; 18 for(k=0;k<4;++k) 19 { 20 d = 1; 21 while(valid(r + d * Dr[k]) && valid(c + d * Dc[k])) 22 { 23 if(M[who][r + d * Dr[k]][c + d * Dc[k]] == -1) 24 { 25 M[who][r + d * Dr[k]][c + d * Dc[k]] = v; 26 if(M[1 - who][r + d * Dr[k]][c + d * Dc[k]] != -1) 27 return M[who][r + d * Dr[k]][c + d * Dc[k]] + M[1 - who][r + d * Dr[k]][c + d * Dc[k]]; 28 } 29 d++; 30 } 31 } 32 return -1; 33 } 34 int howManyMoves(int r1, int c1, int r2, int c2){ 35 if(r1 == r2 && c1 == c2)return 0; 36 if(abs(r1 - r2) == abs(c1 - c2))return 1; 37 memset(M,-1,sizeof M); 38 int res; 39 M[0][r1][c1] = M[1][r2][c2] = 0; 40 res = walk(0,r1,c1,1); 41 if(res != -1)return res; 42 res = walk(1,r2,c2,1); 43 if(res != -1)return res; 44 while(!Q1.empty())Q1.pop(); 45 while(!Q2.empty())Q2.pop(); 46 Q1.push(make_pair(r1,c1)); 47 Q2.push(make_pair(r2,c2)); 48 P h1,h2; 49 while(!Q1.empty() || !Q2.empty()) 50 { 51 if(!Q1.empty()) 52 { 53 h1 = Q1.front(); 54 res = walk(0,h1.first,h1.second,M[0][h1.first][h1.second] + 1); 55 if(res != -1)return res; 56 Q1.pop(); 57 } 58 if(!Q2.empty()) 59 { 60 h2 = Q2.front(); 61 res = walk(1,h2.first,h2.second,M[1][h2.first][h2.second] + 1); 62 if(res != -1)return res; 63 Q2.pop(); 64 } 65 } 66 return -1; 67 } 68 };
TopCoder SRM 628 DIV 2,布布扣,bubuko.com
原文：http://www.cnblogs.com/gangduo-shangjinlieren/p/3861473.html