首页 > ACM题库 > HDU-杭电 > HDU 3368-Reversi-枚举-[解题报告]HOJ
2014
03-16

HDU 3368-Reversi-枚举-[解题报告]HOJ

Reversi

问题描述 :

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.
Pseudoforest

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:

Pseudoforest
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:

Pseudoforest
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):

Pseudoforest
Light takes the bottom left option and reverses one piece:

Pseudoforest
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?

输入:

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.

输出:

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.

样例输入:

3
********
********
********
***LD***
***DL***
********
********
********

********
********
**DLL***
**DLLL**
**DLD***
********
********
********

********
********
*D******
*DLLD***
***LL***
**D*D***
********
********

样例输出:

Case 1: 1
Case 2: 3
Case 3: 0

题意看不懂的直接看百度百科对黑白棋的解释。。。

做法:分情况讨论,一共8个方向。

Reversi

/*
 搜索
 */
 #include<stdio.h>
 #include<string.h>
 const int maxn = 10;
 char mat[ maxn ][ maxn ];
 const int dx[]={-1,1,-1,1};
 const int dy[]={1,-1,-1,1};
 
 int max( int a,int b ){
     return a>b?a:b;
 }
 
 bool in( int x,int y ){
     if( x>=1&&x<=8&&y>=1&&y<=8 ) return true;
     else return false;
 }
 
 int solve( int x,int y ){
     int ans = 0;
     int pos;
 
     pos = -1;
     for( int i=y+1;i<=8;i++ ){
         if( mat[x][i]=='D' ){
             pos = i;
             break;
         }
     }
     if( pos!=-1 ){
         for( int i=y+1;i<=pos;i++ ){
             if( mat[x][i]=='*' ){
                 pos = -1;
                 break;
             }
         }
     }
     if( pos!=-1 ){
         for( int i=y+1;i<=pos;i++ ){
             if( mat[x][i]=='L' )
                 ans++;
         }
     }
     //right
     pos = -1;
     for( int i=y-1;i>=1;i-- ){
         if( mat[x][i]=='D' ){
             pos = i;
             break;
         }
     }
     if( pos!=-1 ){
         for( int i=y-1;i>=pos;i-- ){
             if( mat[x][i]=='*' ){
                 pos = -1;
                 break;
             }
         }
     }
     if( pos!=-1 ){
         for( int i=y-1;i>=pos;i-- ){
             if( mat[x][i]=='L' )
                 ans++;
         }
     }
     //left
     pos = -1;
     for( int i=x+1;i<=8;i++ ){
         if( mat[i][y]=='D' ){
             pos = i;
             break;
         }
     }
     if( pos!=-1 ){
         for( int i=x+1;i<=pos;i++ ){
             if( mat[i][y]=='*' ){
                 pos = -1;
                 break;
             }
         }
     }
     if( pos!=-1 ){
         for( int i=x+1;i<=pos;i++ ){
             if( mat[i][y]=='L' )
                 ans++;
         }
     }
     //down
     pos = -1;
     for( int i=x-1;i>=1;i-- ){
         if( mat[i][y]=='D' ){
             pos = i;
             break;
         }
     }
     if( pos!=-1 ){
         for( int i=x-1;i>=pos;i-- ){
             if( mat[i][y]=='*' ){
                 pos = -1;
                 break;
             }
         }
     }
     if( pos!=-1 ){
         for( int i=x-1;i>=pos;i-- ){
             if( mat[i][y]=='L' )
                 ans++;
         }
     }
     //up
     int posx,posy;
     int K;
     posx = -1;
     for( int k=1;k<=8;k++ ){
         int tx = x+k*dx[0];
         int ty = y+k*dy[0];
         if( in(tx,ty)==false ) break;
         if( mat[tx][ty]=='D' ){
             posx = tx;
             posy = ty;
             K = k;
             break;
         }
     }
     if( posx!=-1 ){
         for( int k=1;k<=K;k++ ){
             int tx = x+k*dx[0];
             int ty = y+k*dy[0];
             if( in(tx,ty)==false ) break;
             if( mat[tx][ty]=='*' ){
                 posx = -1;
                 break;
             }
         }
     }
     if( posx!=-1 ){
         for( int k=1;k<=K;k++ ){
             int tx = x+k*dx[0];
             int ty = y+k*dy[0];
             if( in(tx,ty)==false ) break;
             if( mat[tx][ty]=='L' )
                 ans++;
         }
     }
     //right && up
     posx = -1;
     for( int k=1;k<=8;k++ ){
         int tx = x+k*dx[1];
         int ty = y+k*dy[1];
         if( in(tx,ty)==false ) break;
         if( mat[tx][ty]=='D' ){
             posx = tx;
             posy = ty;
             K = k;
             break;
         }
     }
     if( posx!=-1 ){
         for( int k=1;k<=K;k++ ){
             int tx = x+k*dx[1];
             int ty = y+k*dy[1];
             if( in(tx,ty)==false ) break;
             if( mat[tx][ty]=='*' ){
                 posx = -1;
                 break;
             }
         }
     }
     if( posx!=-1 ){
         for( int k=1;k<=K;k++ ){
             int tx = x+k*dx[1];
             int ty = y+k*dy[1];
             if( in(tx,ty)==false ) break;
             if( mat[tx][ty]=='L' )
                 ans++;
         }
     }
     //left && down
     posx = -1;
     for( int k=1;k<=8;k++ ){
         int tx = x+k*dx[2];
         int ty = y+k*dy[2];
         if( in(tx,ty)==false ) break;
         if( mat[tx][ty]=='D' ){
             posx = tx;
             posy = ty;
             K = k;
             break;
         }
     }
     if( posx!=-1 ){
         for( int k=1;k<=K;k++ ){
             int tx = x+k*dx[2];
             int ty = y+k*dy[2];
             if( in(tx,ty)==false ) break;
             if( mat[tx][ty]=='*' ){
                 posx = -1;
                 break;
             }
         }
     }
     if( posx!=-1 ){
         for( int k=1;k<=K;k++ ){
             int tx = x+k*dx[2];
             int ty = y+k*dy[2];
             if( in(tx,ty)==false ) break;
             if( mat[tx][ty]=='L' )
                 ans++;
         }
     }
     //left &&up
     posx = -1;
     for( int k=1;k<=8;k++ ){
         int tx = x+k*dx[3];
         int ty = y+k*dy[3];
         if( in(tx,ty)==false ) break;
         if( mat[tx][ty]=='D' ){
             posx = tx;
             posy = ty;
             K = k;
             break;
         }
     }
     if( posx!=-1 ){
         for( int k=1;k<=K;k++ ){
             int tx = x+k*dx[3];
             int ty = y+k*dy[3];
             if( in(tx,ty)==false ) break;
             if( mat[tx][ty]=='*' ){
                 posx = -1;
                 break;
             }
         }
     }
     if( posx!=-1 ){
         for( int k=1;k<=K;k++ ){
             int tx = x+k*dx[3];
             int ty = y+k*dy[3];
             if( in(tx,ty)==false ) break;
             if( mat[tx][ty]=='L' )
                 ans++;
         }
     }
     //right && down
 
     return ans;
 }
 
 int main(){
     int T;
     scanf("%d",&T);
     int ca = 1;
     while( T-- ){
         for( int i=1;i<=8;i++ ){
             scanf("%s",mat[i]+1);
         }
         //memset( vis,false,sizeof( vis ) );
         int ans = 0;
         for( int i=1;i<=8;i++ ){
             for( int j=1;j<=8;j++ ){
                 if( mat[i][j]=='*' ){
                     ans = max( ans,solve( i,j ) );
                     //if( ans>0 ) printf("attention:%d %d \n",i,j);
                 }
             }
         }
         printf("Case %d: %d\n",ca++,ans);
     }
     return 0;
 }

View Code

 

参考:http://www.cnblogs.com/justforgl/archive/2013/07/18/3197598.html