下棋

Accepts: 345 Submissions: 2382 Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Problem Description

N?M? 的棋盤上有一個受傷的國王與一個要去救援國王的騎士，他們每個單位時間必須同時移動一次尋找對方。如下圖所示，黑色的圖例表示國王（右）或騎士（左）當前所在的位置，那么灰色的位置表示在一次移動中他們可能到達的位置。國王傷勢嚴重，因此他必須在K個單位時間內得到騎士的救援，否則會掛掉。問國王是否可以在K個單位時間內獲得救援，如果可以，最短需要花多少個單位時間。

Input

第一行包含一個整數 T,（1≤T≤50）? 代表測試數據的組數，接下來 T? 組測試數據。 每組測試數據第一行包含三個整數 N,M,K? , 且 2≤N,M≤1000? , 1≤K≤200? 。第二行兩個整數 X?king?,Y?king?? ，對應國王所在方格的坐標。第三行兩個整數 X?knight?,Y?knight?? ，對應騎士所在方格的坐標。其中 1≤X?king?,X?knight?≤N,1≤Y?king?,Y?knight?≤M? ,保證騎士與國王一開始不在同一個方格內且他們都可以移動。：

Output

對于每組測試數據，輸出兩行： 第一行輸出："Case #i:"。 i? 代表第 i? 組測試數據。 第二行輸出測試數據的結果，如果國王可以得到救援，則輸出最快需要花多少個單位時間。否則，輸出“OH,NO!”。

Sample Input 2 3 2 1 1 1 3 1 3 3 1 1 1 1 2 Sample Output Case #1: 1 Case #2: OH,NO! Statistic | Submit | Clarifications | Back BestCoder Contest System 2.0 題解一： //方法是雙向BFS加特殊判斷#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> using namespace std; const int maxn=1000+5;/*這是位置數組*/ int xk[8]= {-1,0,-1,1,-1,1,0,1}; int yk[8]= {-1,-1,0,1,1,-1,1,0}; int xnk[8]= {-1,-2,-2,-1,1,2,2,1}; int ynk[8]= {-2,-1,1,2,-2,-1,1,2};int T,N,M,K,kingx,kingy,kningx,kningy; int kingstep[maxn][maxn];//國王的最少步的記錄 int kningstep[maxn][maxn];//騎士最少步的記錄（可以不設，直接在BFS中進行判斷） bool vis[maxn][maxn];//是否訪問過//結構體，y代表著縱坐標,x代表著橫坐標 struct POS {int x,y,step;POS(int x,int y,int step) {this->x=x;this->y=y;this->step=step;} };//求國王的最少步 void BFS1() {queue<POS>G;memset(vis,false,sizeof(vis));memset(kingstep,-1,sizeof(kingstep));//代表現在都不能到達G.push(POS(kingx,kingy,0));vis[kingy][kingx]=true;while(!G.empty()) {POS CUR=G.front();G.pop();kingstep[CUR.y][CUR.x]=CUR.step;for(int i=0; i<8; i++) {int nx=CUR.x+xk[i];int ny=CUR.y+yk[i];if(nx>N||nx<1||ny>M||ny<1||vis[ny][nx])continue;vis[ny][nx]=true;G.push(POS(nx,ny,CUR.step+1));}} }//求騎士的最少步（可以去掉這一部分代碼，將這部分代碼簡寫在第一個BFS中，只要加個判斷，大家可以試試） void BFS2() {int cnt=0;queue<POS>G;memset(vis,false,sizeof(vis));memset(kningstep,-1,sizeof(kningstep));//代表現在都不能到達G.push(POS(kningx,kningy,0));vis[kningy][kningx]=true;while(!G.empty()) {POS CUR=G.front();G.pop();kningstep[CUR.y][CUR.x]=CUR.step;for(int i=0; i<8; i++) {int nx=CUR.x+xnk[i];int ny=CUR.y+ynk[i];if(nx>N||nx<1||ny>M||ny<1||vis[ny][nx])continue;vis[ny][nx]=true;G.push(POS(nx,ny,CUR.step+1));}} }int main() {freopen("D://imput.txt","r",stdin);scanf("%d",&T);for(int i=1; i<=T; i++) {scanf("%d%d%d",&N,&M,&K);scanf("%d%d",&kingx,&kingy);scanf("%d%d",&kningx,&kningy);BFS1();BFS2();int maxs=1100000;//目的是得到最少步for(int k=1; k<=M; k++) {for(int j=1; j<=N; j++) {if(kingstep[k][j]!=-1&&kningstep[k][j]!=-1) {//首先必須可以到達int temp;if(kningstep[k][j]>kingstep[k][j]) {//當騎士的步數打與國王時，只需要記錄騎士的步數temp=kningstep[k][j]; //原因是因為，國王的移動方向是相鄰的八個位置，當騎士的步數大于國王時，不管} else { //不管這之間差多少，不管是奇數還是偶數，國王都能在這相差多少的范圍內到達指定的位置）//就是騎士所在的位置。if((kingstep[k][j]-kningstep[k][j])%2==0) {//由于騎士的走法特殊，所以當他的步數少了的時候，那么就得在原地來回走偶數步，//回到回來的位置與國王相遇temp=kingstep[k][j];//國王的步數大。記錄國王的步數} else {temp=kingstep[k][j]+1;//跟騎士的步數大于國王有點類似，當相差奇數的時候，國王不許要多花一步才能與騎士相遇。}}maxs=min(maxs,temp);//得到所有步數中最少的}}}printf("Case #%d:\n",i);if(K>=maxs) {//在規定的時間內找到的話輸出答案。printf("%d\n",maxs);} else {printf("OH,NO!\n");}}return 0; }
題解二：找規律 //此方法就是找規律找取邊以及國王騎士移動的規律 #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> 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 ; }
復制去Google翻譯 翻譯結果

總結

以上是生活随笔為你收集整理的bestCoder 百度之星程序设计资格赛 1005下棋的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。