下棋
Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
N∗M的棋盘上有一个受伤的国王与一个要去救援国王的骑士，他们每个单位时间必须同时移动一次寻找对方。如下图所示，黑色的图例表示国王（右）或骑士（左）当前所在的位置，那么灰色的位置表示在一次移动中他们可能到达的位置。国王伤势严重，因此他必须在K个单位时间内得到骑士的救援，否则会挂掉。问国王是否可以在K个单位时间内获得救援，如果可以，最短需要花多少个单位时间。
Problem's Link: http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=584&pid=1005
Mean:
略。
analyse:
找规律，广搜莫名超时...
Time complexity: O(n)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-05-25-14.59 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; int n , m , k; int main() { int t , len , cas = 0 , i , j ; char ch ; scanf( "%d", &t ); while ( cas < t ) { int x , y , xx, yy , ans , a , b ; cas++; printf( "Case #%d:\n", cas ); scanf( "%d%d%d", &n, &m, &k ); scanf( "%d%d", &x, &y ); scanf( "%d%d", &xx, &yy ); a = abs( x - xx ) ; b = abs( y - yy ) ; if ( ( a == 2 && b == 1 && ( y == 1 || y == m ) ) || ( a == 1 && b == 2 && ( x == 1 || x == n ) ) ) { ans = 2; } else if ( a == 1 && b == 1 && ( x == 1 || x == n ) && ( y == 1 || y == m ) ) { ans = 2 ; } else if ( ( a == 0 && b == 1 && ( y == 1 || y == m ) ) || ( a == 1 && b == 0 && ( x == 1 || x == n ) ) ) { ans = 2 ; } else { if ( a < b ) { int g = a ; a = b ; b = g ; } if ( a / 3 * 2 <= b ) { ans = ( a + b ) / 5 ; if ( ( a + b ) % 5 ) { ans ++ ; } } else { ans = a / 3 ; if ( a % 3 ) { ans ++ ; } } } if ( ans > k ) { printf( "OH,NO!\n" ); } else { printf( "%d\n", ans ); } } return 0 ; }
