ENUQ OJ --1016: Roliygu and Yila
题目描述：
Roliygu is famous because he likes to play games. Today he puts a chessboard in the desktop,and plays a game with Yilan. The size of the chessboard is n by n. A stone is placed in a corner square. They play alternatively with Roliygu having the first move. Each time,player is allowed to move the stone to an unvisited neighbor square horizontally or vertically. The one who can't make a move will lose the game.If both play perfectly, who will win the game?
输入：
The input is a sequence of positive integers each in a separate line. The integers are between 1 and 10 000,inclusive,indicating the size of the chessboard. The end of the input is indicated by a zero.
输出：
Output the winner("Roliygu" or "Yilan") for each input line except the last zero. No other characters should be inserted in the output.
样例输入
2
0
样例输出
Roliygu
题目大意是说桌面上有一个n*n大小的棋盘，在期盘其中一个角落的格子里放有一个石子。Roliygu和Yilan每次将石子移动一格，而且每次只能将石子水平或垂直移向其相邻的且未被石子走过的格子，直到谁最终不能够将石子移动谁就是输家，相应的对方就是赢家。规定：Roliygu移第一步，并且他们每个人每一步都走得很完美。
输入为n表示棋盘的大小，当n = 0时，退出游戏；输出为最终的赢家。
这个题目你需要注意标注红色的文字（并且他们每个人每一步都走得很完美）。这句话的意思是说他们移动的总步数应该竟可能的长，最长就是n*n，也就是说走满棋盘时就分出胜负。如果你在图纸上走一遍你大概很容易就发现当棋盘的大小n是偶数时赢家是Roliygu,当棋盘的大小n实奇数时赢家是Yilan。如果你没有注意到那句话那可能跟我一样提交很多次都不能AC。
所以问题就变成判断n的奇偶性，这个很容易。ac代码如下：
#include<iostream>
using namespace std;
int main() {
int n;
while (cin >> n && n != 0) {
if (n % 2 == 0)
cout << "Roliygu" << endl;
else
cout << "Yilan" << endl;
}
system("pause");
return 0;
}
显然，一开始我是没有注意到那句话的，所以我原本的思路不是判断奇偶。以下是我原本的思路：
假定石子一开始是在棋盘的最左上角的格子里。
我们用一个整型的二维数组来表示棋盘，用 1 表示格子有石子或被石子走过，0 表示为走过的格子，如下一个 3*3 的初始棋盘：
1 0 0
0 0 0
0 0 0
我们将玩家也就是Roloygu和Yilan先保存在一个数组中：
const string Player[2] = { "Yilan","Roliygu" };
每一次移动石子前，我们需要判断石子的四个方向是否是可以到达的。所以我们需要表示我们的方向,我们可以用四个不同数组表示方向，并将他们也存在数组中：
const int D[4] = {1, 2, -1, -2}; //方向：下，右，上，左
模拟石子移动：
模拟玩家移动石子的想法是，每次都随机的向四个方向试探，如果试探到该方向的格子是可到达的就将该格子置为 1 。如果四个方向都是不可到达的就将退出，并判断赢家。
但是，在试探过程中有一个问题，那就是在棋盘边界时，如果你任然随机向四个方向试探的话很可能会造成数组访问越界的麻烦。所以你需要对四条边界做特殊处理，但是四条边界可试探的方向是不同，所以你需要做 4 次特殊处理，这给我们的编码带来麻烦。为了避免这个麻烦我想到的方法是将存放棋盘的二维数组扩大,并将我们真正有效的棋盘放在数组的中间，保存棋盘的空间的周围的值赋值为非零数（假设为 2）这样我们对有效棋盘的处理就不用考虑边界了。3*3的有效棋盘其存储数组应为4x4,如下示：
2 2 2 2 2
2 1 0 0 2
2 0 0 0 2
2 0 0 0 2
2 2 2 2 2
赢家的判断：
我们可以通过最终的有效步数来判断，因为第一步是Roliygu走的，第二步是Yilan走的,既是奇数步是Roliygu,偶数步是Yilan。所以我们只需判断最终的有效步数的奇偶，若为奇数则Roliygu赢，否则Yilan赢。
实现代码：
#include<iostream>
#include<cmath>
#include<ctime>
#include<string>
using namespace std;
const int D[4] = {1, 2, -1, -2}; //方向：下，右，上，左
const string Player[2] = { "Yilan","Roliygu" }; //保存玩家
//动态分配棋盘空间
void malloc_2D(int **&CB,const int n) {
CB = new int*[n];
for (int i = 0; i < n; i++)
CB[i] = new int[n];
}
//初始换棋盘
void init_2D(int **CB, const int n) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
CB[i][j] = 0;
if (i == 0 || j == 0||i==n||j==n)CB[i][j] = 2;
if (i == 1 && j == 1)CB[i][j] = 1;
}
}
}
//打印棋盘
void print_2D(int **CB,const int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << CB[i][j] << " ";
}
cout << endl;
}
}
//释放内存
void free_2D(int **CB,const int n) {
for (int i = 0; i < n; i++)
delete[] CB[i];
delete[]CB;
}
//模拟移动
void playGame(int **CB,int n) {
int x = 1, y = 1;
int step = 0; //统计有效步数
int d;
srand((unsigned int)time(NULL));
while (true){
d = D[rand() % 4]; //随机获得方向
if (d == 1) {
if (CB[x + 1][y] == 0) {
x += 1;
step++;
CB[x][y] = 1;
}
}
else if (d == 2) {
if (CB[x][y + 1] == 0) {
y += 1;
step++;
CB[x][y] = 1;
}
}
else if(d==-1){
if (CB[x - 1][y] == 0) {
x -= 1;
step++;
CB[x][y] = 1;
}
}
else {
if (CB[x][y - 1] == 0) {
y -= 1;
step++;
CB[x][y] = 1;
}
}
if (CB[x+1][y]!=0&&CB[x-1][y]!=0&&CB[x][y+1]!=0&&CB[x][y-1]!=0)break;
}
cout << Player[step % 2] << endl;
}
int main() {
int n;
while (cin >> n && n != 0) {
int **chessboard = NULL;
malloc_2D(chessboard, n+2);
init_2D(chessboard, n+1);
playGame(chessboard, n+2);
free_2D(chessboard, n+2);
}
system("pause");
return 0;
}
