Reversi
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1047 Accepted Submission(s): 430
Problem Description
Reversi, also called Othello, is a two-sided game.
Each of the two sides corresponds to one player; they are referred to here as light and dark after the sides of Othello pieces, but "heads" and "tails" would identify them equally as well, so long as each marker has sufficiently distinctive sides.
Originally, Reversi did not have a defined starting position. Later it adopted Othello's rules, which state that the game begins with four markers placed in a square in the middle of the grid, two facing light-up, two pieces with the dark side up. The dark player makes the first move.
Dark must place a piece with the dark side up on the board, in such a position that there exists at least one straight (horizontal, vertical, or diagonal) occupied line between the new piece and another dark piece, with one or more contiguous light pieces between them. In the below situation, dark has the following options indicated by transparent pieces:
After placing the piece, dark turns over (flips, captures) all light pieces lying on a straight line between the new piece and any anchoring dark pieces. All reversed pieces now show the dark side, and dark can use them in later moves—unless light has reversed them back in the meantime. In other words, a valid move is one where at least one piece is reversed.
If dark decided to put a piece in the topmost location (all choices are strategically equivalent at this time), one piece gets turned over, so that the board appears thus:
Now light plays. This player operates under the same rules, with the roles reversed: light lays down a light piece, causing a dark piece to flip. Possibilities at this time appear thus (indicated by transparent pieces):
Light takes the bottom left option and reverses one piece:
Players take alternate turns. If one player cannot make a valid move, play passes back to the other player. When neither player can move, the game ends. This occurs when the grid has filled up, or when one player has no more pieces on the board, or when neither player can legally place a piece in any of the remaining squares. The player with the most pieces on the board at the end of the game wins.
Now after several rounds, it’s dark’s turn. Can you figure out the largest number of light pieces he can turn over?
Input
The first line contains one integer T representing the number of test cases.
For each test case, there’re 8 lines. Each line contains 8 characters (D represents dark, L represents light, * represents nothing here).
Every two adjacent cases are separated by a blank line.
Output
For each test case, in one line print the case number and the largest number of light pieces the dark player can turn over. If he can’t put one piece in any position, then print 0.
Please follow the format of the sample output.
Sample Input
3
********
********
********
***LD***
***DL***
********
********
********
********
********
**DLL***
**DLLL**
**DLD***
********
********
********
********
********
*D******
*DLLD***
***LL***
**D*D***
********
********
Sample Output
Case 1: 1
Case 2: 3
Case 3: 0
題目大意：首先，給你一副走到一半的棋盤(8*8)，現在輪到黑棋走。規則如下：若新增的黑棋和另外一顆已存在的黑棋之間全是白棋(即沒有空格或另外的黑棋)，例如：黑(new)白白黑(old)，則裡面的白棋全變黑棋，另外，[邊界]白白黑(new)，這種情況不算。問：這顆黑棋放下後，最多能夠翻轉多少顆白棋？(輸入時字母D(Dark)代表黑棋，字母L(Light)代表白棋，*號代表空格。)
簡單分析：遍歷所有棋牌上的位置，若該位置為空，則用一個DFS分別從該位置的8個方向(即上[0,1]，下[0,-1]，左[-1,0]，右[1,0]，左上[-1,-1]，右上[1,-1]，左下[-1,1]，右下[1,1])依次試探。同時把每一個位置最多能夠翻轉的白棋個數存放在變量sum中。
注意這種情況:
*****D**
*****L**
*****L**
*****L**
DLLLL***
********
********
Reversi
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1047 Accepted Submission(s): 430
Problem Description
Reversi, also called Othello, is a two-sided game.
Each of the two sides corresponds to one player; they are referred to here as light and dark after the sides of Othello pieces, but "heads" and "tails" would identify them equally as well, so long as each marker has sufficiently distinctive sides.
Originally, Reversi did not have a defined starting position. Later it adopted Othello's rules, which state that the game begins with four markers placed in a square in the middle of the grid, two facing light-up, two pieces with the dark side up. The dark player makes the first move.
Dark must place a piece with the dark side up on the board, in such a position that there exists at least one straight (horizontal, vertical, or diagonal) occupied line between the new piece and another dark piece, with one or more contiguous light pieces between them. In the below situation, dark has the following options indicated by transparent pieces:
After placing the piece, dark turns over (flips, captures) all light pieces lying on a straight line between the new piece and any anchoring dark pieces. All reversed pieces now show the dark side, and dark can use them in later moves—unless light has reversed them back in the meantime. In other words, a valid move is one where at least one piece is reversed.
If dark decided to put a piece in the topmost location (all choices are strategically equivalent at this time), one piece gets turned over, so that the board appears thus:
Now light plays. This player operates under the same rules, with the roles reversed: light lays down a light piece, causing a dark piece to flip. Possibilities at this time appear thus (indicated by transparent pieces):
Light takes the bottom left option and reverses one piece:
Players take alternate turns. If one player cannot make a valid move, play passes back to the other player. When neither player can move, the game ends. This occurs when the grid has filled up, or when one player has no more pieces on the board, or when neither player can legally place a piece in any of the remaining squares. The player with the most pieces on the board at the end of the game wins.
Now after several rounds, it’s dark’s turn. Can you figure out the largest number of light pieces he can turn over?
Input
The first line contains one integer T representing the number of test cases.
For each test case, there’re 8 lines. Each line contains 8 characters (D represents dark, L represents light, * represents nothing here).
Every two adjacent cases are separated by a blank line.
Output
For each test case, in one line print the case number and the largest number of light pieces the dark player can turn over. If he can’t put one piece in any position, then print 0.
Please follow the format of the sample output.
Sample Input
3
********
********
********
***LD***
***DL***
********
********
********
********
********
**DLL***
**DLLL**
**DLD***
********
********
********
********
********
*D******
*DLLD***
***LL***
**D*D***
********
********
Sample Output
Case 1: 1
Case 2: 3
Case 3: 0
題目大意：首先，給你一副走到一半的棋盤(8*8)，現在輪到黑棋走。規則如下：若新增的黑棋和另外一顆已存在的黑棋之間全是白棋(即沒有空格或另外的黑棋)，例如：黑(new)白白黑(old)，則裡面的白棋全變黑棋，另外，[邊界]白白黑(new)，這種情況不算。問：這顆黑棋放下後，最多能夠翻轉多少顆白棋？(輸入時字母D(Dark)代表黑棋，字母L(Light)代表白棋，*號代表空格。)
簡單分析：遍歷所有棋牌上的位置，若該位置為空，則用一個DFS分別從該位置的8個方向(即上[0,1]，下[0,-1]，左[-1,0]，右[1,0]，左上[-1,-1]，右上[1,-1]，左下[-1,1]，右下[1,1])依次試探。同時把每一個位置最多能夠翻轉的白棋個數存放在變量sum中。
注意這種情況:
*****D**
*****L**
*****L**
*****L**
DLLLL***
********
********
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=10;
char Map[MAX][MAX];
int dir[8][2]={0,1,0,-1,1,0,-1,0,1,1,-1,-1,1,-1,-1,1};
int sum,ans;
void DFS(int x,int y,int i,int num){
if(x<0 || y<0 || x>=8 || y>=8 || Map[x][y] == '*')return;
if(Map[x][y] == 'L')++num;
if(Map[x][y] == 'D'){ans+=num;return;}//表示i這個方向能翻轉num個白棋
DFS(x+dir[i][0],y+dir[i][1],i,num);
}
int main(){
int t,num=0;
cin>>t;
while(t--){
sum=0;
for(int i=0;i<8;++i)cin>>Map[i];
for(int i=0;i<8;++i){
for(int j=0;j<8;++j){
if(Map[i][j] == '*'){
ans=0;
for(int k=0;k<8;++k){//對每個點8個方向進行搜索
DFS(i+dir[k][0],j+dir[k][1],k,0);
}
sum=sum>ans?sum:ans;
}
}
}
cout<<"Case "<<++num<<": "<<sum<<endl;
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=10;
char Map[MAX][MAX];
int dir[8][2]={0,1,0,-1,1,0,-1,0,1,1,-1,-1,1,-1,-1,1};
int sum,ans;
void DFS(int x,int y,int i,int num){
if(x<0 || y<0 || x>=8 || y>=8 || Map[x][y] == '*')return;
if(Map[x][y] == 'L')++num;
if(Map[x][y] == 'D'){ans+=num;return;}//表示i這個方向能翻轉num個白棋
DFS(x+dir[i][0],y+dir[i][1],i,num);
}
int main(){
int t,num=0;
cin>>t;
while(t--){
sum=0;
for(int i=0;i<8;++i)cin>>Map[i];
for(int i=0;i<8;++i){
for(int j=0;j<8;++j){
if(Map[i][j] == '*'){
ans=0;
for(int k=0;k<8;++k){//對每個點8個方向進行搜索
DFS(i+dir[k][0],j+dir[k][1],k,0);
}
sum=sum>ans?sum:ans;
}
}
}
cout<<"Case "<<++num<<": "<<sum<<endl;
}
return 0;
}
