解題區►解題區 - UVa

UVa 844 - Pousse

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

模擬一款推硬幣的遊戲，在一個 N x N 的盤面，可以從上下左右四個方向塞入自己的硬幣。

現在有兩個人輪流玩，一開始由 ‘X’ 作為先手，塞入硬幣的過程中，會將同行或同列的硬幣往前推，如果同一個的硬幣個數大於 N，則末端的硬幣將會掉出盤面。

模擬遊戲，直到其中一個玩家的連線個數大於另一名玩家，連線個數只看行、列皆具有相同硬幣的情況。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT

Sample Output

1
2
3
TIE GAME
X WINS

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h> 
#include <string.h>
char cmd[32767][64];
char g[128][128];
int n;
int isCompleted() {
	int Oline = 0, Xline = 0, cnt;
	char c;
	for (int i = 0; i < n; i++) {
		c = g[i][0], cnt = 0;
		for (int j = 0; g[i][0] == g[i][j] && j < n; cnt++, j++);
		if (cnt == n && c != ' ') {
			Oline += c == 'O';
			Xline += c == 'X';
		}
		c = g[0][i], cnt = 0;
		for (int j = 0; g[0][i] == g[j][i] && j < n; cnt++, j++);
		if (cnt == n && c != ' ') {
			Oline += c == 'O';
			Xline += c == 'X';
		}
	}
	return Oline == Xline ? 0 : (Oline < Xline ? -1 : 1);
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		int m = 0;
		while (scanf("%s", cmd[m]) == 1) {
			if (!strcmp(cmd[m], "QUIT"))
				break;
			m++;
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				g[i][j] = ' ';
		int ret = 0, turn = 0;
		for (int i = 0; i < m; i++, turn = !turn) {
			int x;
			sscanf(cmd[i]+1, "%d", &x);
			x--;
			if (cmd[i][0] == 'L') {
				int idx = 0;
				while (idx < n && g[x][idx] != ' ')	idx++;
				for (int i = idx; i > 0; i--)
					g[x][i] = g[x][i-1];
				g[x][0] = turn ? 'O' : 'X';
			}
			if (cmd[i][0] == 'R') {
				int idx = n-1;
				while (idx > 0 && g[x][idx] != ' ')	idx--;
				for (int i = idx; i < n-1; i++)
					g[x][i] = g[x][i+1];
				g[x][n-1] = turn ? 'O' : 'X';
			}
			if (cmd[i][0] == 'T') {
				int idx = 0;
				while (idx < n && g[idx][x] != ' ')	idx++;
				for (int i = idx; i > 0; i--)
					g[i][x] = g[i-1][x];
				g[0][x] = turn ? 'O' : 'X';
			}			
			if (cmd[i][0] == 'B') {
				int idx = n-1;
				while (idx > 0 && g[idx][x] != ' ')	idx--;
				for (int i = idx; i < n-1; i++)
					g[i][x] = g[i+1][x];
				g[n-1][x] = turn ? 'O' : 'X';
			}
//			for (int i = 0; i < n; i++, puts(""))
//				for (int j = 0; j < n; j++)
//					putchar(g[i][j]);
//			puts("---");
			if (ret = isCompleted())
				break;
		}
		if (ret)
			puts(ret < 0 ? "X WINS" : "O WINS");
		else
			puts("TIE GAME");
		if (testcase)
			puts("");
	}
	return 0;
}
/*
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT
*/