uva220

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

08 12月 2017

Othello is a game played by two people on an 8 x 8 board, using disks that are white on one side and black on the other. One player places disks with the white side up and the other player places disks with the black side up. The players alternate placing one disk on an unoccupied space on the board. In placing a disk, the player must bracket at least one of the other color disks. Disks are bracketed if they are in a straight line horizontally, vertically, or diagonally, with a disk of the current player’s color at each end of the line. When a move is made, all the disks that were bracketed are changed to the color of the player making the move. (It is possible that disks will be bracketed across more than one line in a single move.)

Write a program to read a series of Othello games.

Input

The first line of the input is the number of games to be processed. Each game consists of a board configuration followed by a list of commands. The board configuration consists of 9 lines. The first 8 specify the current state of the board. Each of these 8 lines contains 8 characters, and each of these characters will be one of the following:

‘-’ indicating an unoccupied square

‘B’ indicating a square occupied by a black disk

‘W’ indicating a square occupied by a white disk

The ninth line is either a ‘B’ or a ‘W’ to indicate which is the current player. You may assume that the data is legally formatted.

Then a set of commands follows. The commands are to list all possible moves for the current player, make a move, or quit the current game. There is one command per line with no blanks in the input.

Output

The commands and the corresponding outputs are formatted as follows:

List all possible moves for the current player. The command is an ‘L’ in the first column of the line. The program should go through the board and print all legal moves for the current player in the format (x, y) where x represents the row of the legal move and y represents its column. These moves should be printed in row major order which means:

1) all legal moves in row number i will be printed before any legal move in row number j if j is greater than i and

2) if there is more than one legal move in row number i, the moves will be printed in ascending order based on column number.

All legal moves should be put on one line. If there is no legal move because it is impossible for the current player to bracket any pieces, the program should print the message ‘No legal move.’

Make a move.

The command is an ‘M’ in the first column of the line, followed by 2 digits in the second and third column of the line. The digits are the row and the column of the space to place the piece of the current player’s color, unless the current player has no legal move. If the current player has no legal move, the current player is first changed to the other player and the move will be the move of the new current player. You may assume that the move is then legal. You should record the changes to the board, including adding the new piece and changing the color of all bracketed pieces. At the end of the move, print the number of pieces of each color on the board in the format ‘Black - xx White - yy’ where xx is the number of black pieces on the board and yy is the number of white pieces on the board. After a move, the current player will be changed to the player that did not move.

Quit the current game.

The command will be a ‘Q’ in the first column of the line. At this point, print the final board configuration using the same format as was used in the input. This terminates input for the current game.

You may assume that the commands will be syntactically correct. Put one blank line between output from separate games and no blank lines anywhere else in the output.

Sample Input

2
--------
--------
--------
---WB---
---BW---
--------
--------
--------
W
L
M35
L
Q
WWWWB---
WWWB----
WWB-----
WB------
--------
--------
--------
--------
B
L
M25
L
Q

Sample Output

(3,5) (4,6) (5,3) (6,4)
Black - 1 White - 4
(3,4) (3,6) (5,6)
--------
--------
----W---
---WW---
---BW---
--------
--------
--------
No legal move.
Black - 3 White - 12
(3,5)
WWWWB---
WWWWW---
WWB-----
WB------
--------
--------
--------
--------

题目类型：简单模拟

算法分析：按照题目的要求直接分类模拟输出即可，注意最后一个测试用例的最后没有多余的空行，输出棋子个数时的格式和一个位置可能存在夹住异色棋子的多个状态，下面第一个代码是更好的实现

/**************************************************
filename       :m.cpp
author         :maksyuki
created time   :2017/12/8 20:54:53
last modified  :2017/12/8 22:29:29
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

char ga[16][16];
int gb[16][16];
bool vis[16][16];

struct node {
    int x, y;
    node () {};
    node (int xx, int yy): x(xx), y(yy) {};
};

int len;
node aa[maxn];

bool is_inline(int x, int y) {
    if(x >= 1 && x <= 8 && y >= 1 && y <= 8) return true;
    return false;
}

void findv(int user) {
    for(int i = 1; i <= 8; i++) 
        for(int j = 1; j <= 8; j++) {
            if(gb[i][j]) continue;
            for(int k = 0; k < 8; k++) {
                int tmpx = i + dx[k], tmpy = j + dy[k];
                bool is_change = false;
                while(is_inline(tmpx, tmpy) && user == -gb[tmpx][tmpy]) {
                    tmpx += dx[k], tmpy += dy[k];
                    is_change = true;
                }
                if(is_inline(tmpx, tmpy) && user == gb[tmpx][tmpy] && is_change && !vis[i][j]) {
                    aa[len++] = node(i, j);
                    vis[i][j] = true; 
                }
            }
        }
}

void move(int user, int xx, int yy) {
    gb[xx][yy] = user;
    for(int i = 0; i < 8; i++) {
        int tmpx = xx + dx[i], tmpy = yy + dy[i];
        while(is_inline(tmpx, tmpy) && user == -gb[tmpx][tmpy]) {
            tmpx += dx[i], tmpy += dy[i];
        }
        if(is_inline(tmpx, tmpy) && user == gb[tmpx][tmpy]) {
            int ax = xx, ay = yy;
            while(1) {
                if(ax == tmpx && ay == tmpy) break;
                gb[ax][ay] = user;
                ax += dx[i], ay += dy[i];
            }
        }
    }

    int cntb = 0, cntw = 0;
    for(int i = 1; i <= 8; i++)
        for(int j = 1; j <= 8; j++) {
            if(gb[i][j] == -1) cntb++;
            if(gb[i][j] == 1) cntw++;
        }

    printf("Black -%3d White -%3d\n", cntb, cntw);
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t, id = 1;
    scanf("%d", &t);
    while(t--) {
        for(int i = 1; i <= 8; i++) scanf(" %s", (ga[i] + 1));
       
        memset(gb, 0, sizeof(gb));
        for(int i = 1; i <= 8; i++)
            for(int j = 1; j <= 8; j++) {
                if(ga[i][j] == 'B') gb[i][j] = -1;
                if(ga[i][j] == 'W') gb[i][j] = 1;
            }

        char tmp;
        int user;
        scanf(" %c", &tmp);
        if(tmp == 'B') user = -1;
        else user = 1;
        
        if(id++ > 1) puts("");

        char cmd[16];
        while(scanf(" %s", cmd)) {
            if(!strcmp(cmd, "Q")) {
                for(int i = 1; i <= 8; i++) {
                    for(int j = 1; j <= 8; j++) {
                        if(gb[i][j] == -1) printf("B");
                        if(gb[i][j] == 0) printf("-");
                        if(gb[i][j] == 1) printf("W");
                    }
                    puts("");
                }
                break;
            }

            if(!strcmp(cmd, "L")) {
                len = 0;
                memset(vis, false, sizeof(vis));
                findv(user);
                if(!len) puts("No legal move.");
                else {
                    for(int i = 0; i < len; i++) {
                        if(i) printf(" ");
                        printf("(%d,%d)", aa[i].x, aa[i].y);
                    }
                    puts("");
                }
            }
            
            else {
                int xx = cmd[1] - '0', yy = cmd[2] - '0';
                len = 0;
                memset(vis, false, sizeof(vis));
                findv(user);             
                if(!len) user = -user;
                move(user, xx, yy); 
                user = -user;
            }
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

/**************************************************

filename :m.cpp

author :maksyuki

created time :2017/12/8 20:54:53

last modified :2017/12/8 22:29:29

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};

const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

char ga[16][16];

int gb[16][16];

bool vis[16][16];

struct node {

int x, y;

node () {};

node (int xx, int yy): x(xx), y(yy) {};

};

int len;

node aa[maxn];

bool is_inline(int x, int y) {

if(x >= 1 && x <= 8 && y >= 1 && y <= 8) return true;

return false;

}

void findv(int user) {

for(int i = 1; i <= 8; i++)

for(int j = 1; j <= 8; j++) {

if(gb[i][j]) continue;

for(int k = 0; k < 8; k++) {

int tmpx = i + dx[k], tmpy = j + dy[k];

bool is_change = false;

while(is_inline(tmpx, tmpy) && user == -gb[tmpx][tmpy]) {

tmpx += dx[k], tmpy += dy[k];

is_change = true;

}

if(is_inline(tmpx, tmpy) && user == gb[tmpx][tmpy] && is_change && !vis[i][j]) {

aa[len++] = node(i, j);

vis[i][j] = true;

}

void move(int user, int xx, int yy) {

gb[xx][yy] = user;

for(int i = 0; i < 8; i++) {

int tmpx = xx + dx[i], tmpy = yy + dy[i];

while(is_inline(tmpx, tmpy) && user == -gb[tmpx][tmpy]) {

tmpx += dx[i], tmpy += dy[i];

}

if(is_inline(tmpx, tmpy) && user == gb[tmpx][tmpy]) {

int ax = xx, ay = yy;

while(1) {

if(ax == tmpx && ay == tmpy) break;

gb[ax][ay] = user;

ax += dx[i], ay += dy[i];

}

int cntb = 0, cntw = 0;

for(int i = 1; i <= 8; i++)

for(int j = 1; j <= 8; j++) {

if(gb[i][j] == -1) cntb++;

if(gb[i][j] == 1) cntw++;

}

printf("Black -%3d White -%3d\n", cntb, cntw);

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t, id = 1;

scanf("%d", &t);

while(t--) {

for(int i = 1; i <= 8; i++) scanf(" %s", (ga[i] + 1));

memset(gb, 0, sizeof(gb));

for(int i = 1; i <= 8; i++)

for(int j = 1; j <= 8; j++) {

if(ga[i][j] == 'B') gb[i][j] = -1;

if(ga[i][j] == 'W') gb[i][j] = 1;

}

char tmp;

int user;

scanf(" %c", &tmp);

if(tmp == 'B') user = -1;

else user = 1;

if(id++ > 1) puts("");

char cmd[16];

while(scanf(" %s", cmd)) {

if(!strcmp(cmd, "Q")) {

for(int i = 1; i <= 8; i++) {

for(int j = 1; j <= 8; j++) {

if(gb[i][j] == -1) printf("B");

if(gb[i][j] == 0) printf("-");

if(gb[i][j] == 1) printf("W");

}

puts("");

}

break;

}

if(!strcmp(cmd, "L")) {

len = 0;

memset(vis, false, sizeof(vis));

findv(user);

if(!len) puts("No legal move.");

else {

for(int i = 0; i < len; i++) {

if(i) printf(" ");

printf("(%d,%d)", aa[i].x, aa[i].y);

}

puts("");

}

else {

int xx = cmd[1] - '0', yy = cmd[2] - '0';

len = 0;

memset(vis, false, sizeof(vis));

findv(user);

if(!len) user = -user;

move(user, xx, yy);

user = -user;

}

return 0;

}

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

const int dx[] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 1};

const int maxn = 12;

char game[maxn][maxn];
int sum_b, sum_w;
char cur_player;

void CalcNumber ()
{
	sum_b = 0, sum_w = 0;

	int i, j;
	for (i = 0; i < 8; i++)
		for (j = 0; j < 8; j++)
		{
			if (game[i][j] == 'W')
				sum_w++;

			else if (game[i][j] == 'B')
				sum_b++;
		}
}


void OutPut ()
{
	int i;
	for (i = 0; i < 8; i++)
		cout << game[i] << endl;
}

inline char Opposite (char val)
{
	if (val == 'B')
		return 'W';

return 'B';
}

void Change (char &val)
{
	if (val == 'B')
		val = 'W';

	else
		val = 'B';
}


inline bool OkMove (int x, int y)
{
	if (x >= 0 && x <= 7 && y >= 0 && y <= 7 && game[x][y] == Opposite (cur_player))
		return true;

return false;
}

void PaintPoint (int x, int y, int loc)
{
	game[x][y] = cur_player;
	while (OkMove (x + dx[loc], y + dy[loc]))
	{
		x += dx[loc];
		y += dy[loc];
		game[x][y] = cur_player;
	}
}


bool Search (int x, int y, int loc)
{

	while (OkMove (x + dx[loc], y + dy[loc]))
	{
		x += dx[loc];
		y += dy[loc];
	}

	int temp_x = x + dx[loc];
	int temp_y = y + dy[loc];

	if (temp_x >= 0 && temp_x <= 7 && temp_y >= 0 && temp_y <= 7
	&& game[temp_x][temp_y] == cur_player)
		return true;

return false;
}

void ShowLegalPosition ()
{
	bool is_first = true;

	int i;
	for (i = 0; i < 8; i++)
	{
		int j;
		for (j = 0; j < 8; j++)
		{
			int k;
			for (k = 0; k < 8; k++)
				if (game[i][j] == '-' && OkMove (i + dx[k], j + dy[k]))
				{	//game[i][j] == '-' is important!!!
						if (Search (i, j, k))
						{
							if (is_first)
							{
								is_first = false;
								cout << "(" << i + 1 << "," << j + 1 << ")";
							}

							else
								cout << " (" << i + 1 << "," << j + 1 << ")";

						break;	//important!!!!!!

						}

				}
		}
	}

	if (is_first)
		cout << "No legal move." << endl;

	else
		cout << endl;
}

bool PlayGame (int x, int y)
{
	bool is_legal = false;

	int i;
	for (i = 0; i < 8; i++)
		if (OkMove (x + dx[i], y + dy[i]))
		{
			if (Search (x, y, i))
			{
				is_legal = true;
				PaintPoint (x, y, i);
			}
		}

return is_legal;
}


int main()
{
//	ifstream cin ("aaa.txt");

	int cases;
	cin >> cases;
	char cmd[12];

	while (cases--)
	{
		int i;
		sum_b = 0, sum_w = 0;

		for (i = 0; i < 8; i++)
		{
			int j;
			for (j = 0; j < 8; j++)
			{
				cin >> game[i][j];

				if (game[i][j] == 'W')
					sum_w++;

				else if (game[i][j] == 'B')
				sum_b++;
			}
		}

		cin >> cur_player;
		while (cin >> cmd)
		{
			if (cmd[0] == 'Q')
			{
				OutPut ();
				break;
			}

			else if (cmd[0] == 'L')
			{
				ShowLegalPosition ();
			}

			else if (cmd[0] == 'M')
			{
				int weizhi_x = (cmd[1] - '0') - 1;
				int weizhi_y = (cmd[2] - '0') - 1;
				if (game[weizhi_x][weizhi_y] == '-' && PlayGame (weizhi_x, weizhi_y))
				{
					Change (cur_player);
				}

				else
				{
					Change (cur_player);
					PlayGame (weizhi_x, weizhi_y);
					Change (cur_player);
				}

				CalcNumber ();
				cout << "Black -" << setw (3) << sum_b << " ";
				cout << "White -" << setw (3) << sum_w << endl;
			}
		}

		if (cases)
			cout << endl;
	}

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

#include <iostream>

#include <fstream>

#include <iomanip>

using namespace std;

const int dx[] = {-1, -1, -1, 1, 1, 1, 0, 0};

const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 1};

const int maxn = 12;

char game[maxn][maxn];

int sum_b, sum_w;

char cur_player;

void CalcNumber ()

{

sum_b = 0, sum_w = 0;

int i, j;

for (i = 0; i < 8; i++)

for (j = 0; j < 8; j++)

{

if (game[i][j] == 'W')

sum_w++;

else if (game[i][j] == 'B')

sum_b++;

}

void OutPut ()

{

int i;

for (i = 0; i < 8; i++)

cout << game[i] << endl;

}

inline char Opposite (char val)

{

if (val == 'B')

return 'W';

return 'B';

}

void Change (char &val)

{

if (val == 'B')

val = 'W';

else

val = 'B';

}

inline bool OkMove (int x, int y)

{

if (x >= 0 && x <= 7 && y >= 0 && y <= 7 && game[x][y] == Opposite (cur_player))

return true;

return false;

}

void PaintPoint (int x, int y, int loc)

{

game[x][y] = cur_player;

while (OkMove (x + dx[loc], y + dy[loc]))

{

x += dx[loc];

y += dy[loc];

game[x][y] = cur_player;

}

bool Search (int x, int y, int loc)

{

while (OkMove (x + dx[loc], y + dy[loc]))

{

x += dx[loc];

y += dy[loc];

}

int temp_x = x + dx[loc];

int temp_y = y + dy[loc];

if (temp_x >= 0 && temp_x <= 7 && temp_y >= 0 && temp_y <= 7

&& game[temp_x][temp_y] == cur_player)

return true;

return false;

}

void ShowLegalPosition ()

{

bool is_first = true;

int i;

for (i = 0; i < 8; i++)

{

int j;

for (j = 0; j < 8; j++)

{

int k;

for (k = 0; k < 8; k++)

if (game[i][j] == '-' && OkMove (i + dx[k], j + dy[k]))

{ //game[i][j] == '-' is important!!!

if (Search (i, j, k))

{

if (is_first)

{

is_first = false;

cout << "(" << i + 1 << "," << j + 1 << ")";

}

else

cout << " (" << i + 1 << "," << j + 1 << ")";

break; //important!!!!!!

}

if (is_first)

cout << "No legal move." << endl;

else

cout << endl;

}

bool PlayGame (int x, int y)

{

bool is_legal = false;

int i;

for (i = 0; i < 8; i++)

if (OkMove (x + dx[i], y + dy[i]))

{

if (Search (x, y, i))

{

is_legal = true;

PaintPoint (x, y, i);

}

return is_legal;

}

int main()

{

// ifstream cin ("aaa.txt");

int cases;

cin >> cases;

char cmd[12];

while (cases--)

{

int i;

sum_b = 0, sum_w = 0;

for (i = 0; i < 8; i++)

{

int j;

for (j = 0; j < 8; j++)

{

cin >> game[i][j];

if (game[i][j] == 'W')

sum_w++;

else if (game[i][j] == 'B')

sum_b++;

}

cin >> cur_player;

while (cin >> cmd)

{

if (cmd[0] == 'Q')

{

OutPut ();

break;

}

else if (cmd[0] == 'L')

{

ShowLegalPosition ();

}

else if (cmd[0] == 'M')

{

int weizhi_x = (cmd[1] - '0') - 1;

int weizhi_y = (cmd[2] - '0') - 1;

if (game[weizhi_x][weizhi_y] == '-' && PlayGame (weizhi_x, weizhi_y))

{

Change (cur_player);

}

else

{

Change (cur_player);

PlayGame (weizhi_x, weizhi_y);

Change (cur_player);

}

CalcNumber ();

cout << "Black -" << setw (3) << sum_b << " ";

cout << "White -" << setw (3) << sum_w << endl;

}

if (cases)

cout << endl;

}

return 0;

}

uva201

uva253

超客的水墨烟雨

uva220

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						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