下棋

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 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #define LL long long#define ULL unsigned long longusing 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 ;}

View Code