Chinese checkers

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：2 描述

I think almost everyone play Chinese checkers when we were young.?

Recently, hft777 is fond of playing Chinese checkers. But he is puzzled with how many steps at least to move all his pieces to his?opposite?position.

To make the problem simple, now we take a line into account. There are n positions on a line,?numbered from 0 to n-1.At fast, two same balls is on 0 and 1 position, and every time you can move a ball left or right, or you can move a ball on the position x to the position z on the other side of the ball on the position y, and |x-y|=|y-z|. And you must mark sure the ball can’t move out of the bounder, and the two balls can’t be on one same position. Now, hft777 wants to how many steps at least to move the two same to the n-2, n-1 positions.

輸入

The first line of the input is one integer t, the number of testcase.
For each testcase, one integer n for a line, corresponding to the length of the line. 2≤n<1000?

輸出

For each testcase output the minimum steps.

樣例輸入

2 3 4

樣例輸出

1 2

比賽時一直在找規律，但是因為推出的數據有點少，根據這些數據推出的規律是錯的。雖然比賽時也想到了用廣搜寫，但是害怕超時就沒嘗試。現在想想真有點后悔，當時應該試試的。

題意：跳棋。有n個位置，從0~n-1編號，開始時兩個球分別在0、1位置，目標狀態是兩個球在n-2、n-1位置。對于每次操作，可以向左（即向后）走一步，可以向右（即向前）走1步，也可以使一個球跳過另外一個球，跳之前的位置和調之后的位置距離另外一個球的距離相等，且每次操作都必須在0~n-1范圍內。問從0、1位置到n-2、n-1位置最少需要操作多少次。

分析：用廣搜把所有可能出現的情況都求出來，之后每輸入一個值，直接輸出答案即可。

用數組模擬隊列：

//step[i][j]記錄兩個球分別到達i、j點的最小步數 //step[i][j]=0時表示后面的球在i位置、前面的球在j位置這個狀態沒有出現過 #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; const int N = 1010; int step[N][N]; int que[N*N][2]; int head, tail;void bfs(int n) {int x, y, nx, ny;memset(step, 0, sizeof(step));step[0][1] = 0;que[0][0] = 0;que[0][1] = 1;head = 0;tail = 1;while(head < tail){x = que[head][0];y = que[head++][1];if((x == n - 1 && y == n - 2) || (x == n - 2 && y == n - 1))return ;int mmax = max(x, y);int mmin = min(x, y);x = mmin;y = mmax;if(x - 1 > 0) //后面的球向后走1步{nx = x - 1;ny = y;if(!step[nx][ny]){step[nx][ny] = step[x][y] + 1;que[tail][0] = nx;que[tail++][1] = ny;}}if(x + 1 < n && x + 1 != y) //后面的球向前走1步{nx = x + 1;ny = y;if(!step[nx][ny]){step[nx][ny] = step[x][y] + 1;que[tail][0] = nx;que[tail++][1] = ny;}}if(y - 1 > 0 && y - 1 != x) //前面的球向后走1步{nx = x;ny = y - 1;if(!step[nx][ny]){step[nx][ny] = step[x][y] + 1;que[tail][0] = nx;que[tail++][1] = ny;}}if(y + 1 < n) //前面的球向前走一步{nx = x;ny = y + 1;if(!step[nx][ny]){step[nx][ny] = step[x][y] + 1;que[tail][0] = nx;que[tail++][1] = ny;}}if(y * 2 - x < n) //后面的球跨過前面的球向前跳{nx = y;ny = y * 2 - x;if(!step[nx][ny]){step[nx][ny] = step[x][y] + 1;que[tail][0] = nx;que[tail++][1] = ny;}}if(x * 2 - y >= 0) //前面的球跨過后面的球向后跳{nx = x * 2 - y;ny = x;if(!step[nx][ny]){step[nx][ny] = step[x][y] + 1;que[tail][0] = nx;que[tail++][1] = ny;}}} }int main() {int T, n;bfs(1005);scanf("%d",&T);while(T--){scanf("%d",&n);if(n == 2)printf("0\n");elseprintf("%d\n", step[n-2][n-1]);}return 0; }

用STL里面的隊列：

#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> using namespace std;const int N = 1010; struct node {int x;int y; }; int step[N][N];void bfs(int n) {queue <node> que;node a, b, c;memset(step, 0, sizeof(step));a.x = 0;a.y = 1;que.push(a);while(!que.empty()){b = que.front();que.pop();int x = min(b.x, b.y);int y = max(b.x, b.y);if((x == n - 1 && y == n - 2) || (x == n - 2 && y == n - 1))return ;if(x - 1 > 0) //后面的球向后走1步{int nx = x - 1;int ny = y;if(!step[nx][ny]){c.x = nx;c.y = ny;que.push(c);step[nx][ny] = step[x][y] + 1;}}if(x + 1 < n && x + 1 != y) //后面的球向前走1步{int nx = x + 1;int ny = y;if(!step[nx][ny]){c.x = nx;c.y = ny;que.push(c);step[nx][ny] = step[x][y] + 1;}}if(y - 1 != x && y - 1 > 0) //前面的球向后走1步 {int nx = x;int ny = y - 1;if(!step[nx][ny]){c.x = nx;c.y = ny;que.push(c);step[nx][ny] = step[x][y] + 1;}}if(y + 1 < n) //前面的球向前走一步{int nx = x;int ny = y + 1;if(!step[nx][ny]){c.x = nx;c.y = ny;que.push(c);step[nx][ny] = step[x][y] + 1;}}if(y * 2 - x < n) //后面的球跨過前面的球向前跳{int nx = y;int ny = y * 2 - x;if(!step[nx][ny]){c.x = nx;c.y = ny;que.push(c);step[nx][ny] = step[x][y] + 1;}}if(x * 2 - y > 0) //前面的球跨過后面的球向后跳 {int nx = x * 2 - y;int ny = x;if(!step[nx][ny]){c.x = nx;c.y = ny;que.push(c);step[nx][ny] = step[x][y] + 1;}}} }int main() {bfs(1005);int T, n;scanf("%d",&T);while(T--){scanf("%d",&n);if(n == 2)printf("0\n");elseprintf("%d\n",step[n-2][n-1]);}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 692 Chinese checkers（广搜）的全部內容，希望文章能夠幫你解決所遇到的問題。

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