谷歌校园招聘在线笔试题题目一道

写一道吧，2013年第二轮第三题。

这一题在规定的时间内没有做出来，第二天看了一下题目，觉得可以做，谁知道这一做就是一天...

题意描述：

给定一个n*n的棋盘，如下图：

QQ20131014 1 2x

棋盘的上下两端是红色的，左右两端是蓝色的，四个角红色蓝色共享。红色蓝色轮流（先后随机）向棋盘中摆放一个棋子，率先联通两边者获胜（红色联通上下，蓝色联通左右）。求给定状态的棋盘是否合法（impossible,red wins,blue wins, nobody wins）。

这个题目瞬间想到了当时校赛的五子棋是否合法，但是惭愧的是至今没有做出那一个题...

解题思路：

个人觉得这一个题目主要是考验思维的缜密和短时间的代码能力，遗憾的是两者我都没有...

首先是，如何判断获胜？获胜的条件是，左右联通或者上下联通。这里把上下左右四条边，看作四个定点，那么只要存在一条路径将上下联通或者左右联通即是有人获胜。于是我想到了并查集合。将棋盘中每个点都看作一个点，与他相邻的六个点，如果颜色相同，那么即是存在一条边相连，即可把他们union。因此在整个地图输入之后，遍历一边图，即可得到获胜情况。注意的是，我们把四个边当作了四个定点，那么对每一个与边相邻的其他的定点都应当与该边进行一次判断，颜色相同就union。

接下来是如何判断非法情况？

这个问题，一开始觉得很简单，胡乱写了一个交了wa了多次，最后在纸上推敲了半天发现是没有覆盖完全。下面给出我的思路：

首先判断两个棋子差距的绝对值是不是大于。如果大于1，非法。

之后根据胜负情况进行讨论。首先两个都获胜，非法（今天看的时候感觉这种情况不会存在，欢迎大家讨论了）。

当其中有一方获胜的时候：如果红色胜但是蓝色棋子多，非法；蓝色胜红色棋子多同样非法。之外的只有一方胜利的情况下需要找到最后制胜的那枚棋子。找到这枚棋子的方法是，去掉获胜方的一枚棋子，然后判断胜负，如果不能获胜，则说明这是一个关键子，如果没有关键子的话，状态非法。

剩下的状态就是合法状态。

代码：

  1 #include <iostream>
  2 #include <cstring>
  3 
  4 using namespace std;
  5 
  6 const int MAXSIZE = 100+5;
  7 
  8 char map[MAXSIZE][MAXSIZE];
  9 
 10 int state[MAXSIZE*MAXSIZE+4];
 11 
 12 const int nextX[] = {-1,-1,0,0,1,1};
 13 const int nextY[] = {0,1,-1,1,-1,0};
 14 
 15 int n,R,B;
 16 
 17 int UP,LEFT,DOWN,RIGHT;
 18 
 19 int F( int x ) {
 20     int t = x;
 21     while ( state[t] != t ) {
 22     t = state[t];
 23     }
 24     return t;
 25 }
 26 
 27 void U( int x,  int y ) {
 28     if ( x != y ) {
 29     int fx = F(x);
 30     int fy = F(y);
 31     if ( fx != fy ) {
 32     state[fy] = fx;
 33     }
 34     }
 35 }
 36 
 37 void input(){
 38     cin>>n;
 39     R = 0;
 40     B = 0;
 41     UP = n*n;
 42     LEFT = UP+1;
 43     DOWN = LEFT+1;
 44     RIGHT = DOWN+1;
 45     memset(map,0,sizeof(map));
 46     for ( int i = 0; i < n; i++ ) {
 47     for ( int j = 0; j < n; j++ ) {
 48         cin>>map[i][j];
 49         if ( map[i][j] == 'R' ) {
 50         R++;
 51         }
 52         else if ( map[i][j] == 'B' ) {
 53         B++;
 54         }
 55     }
 56     }
 57 
 58 }
 59 
 60 int inrange(int x, int y ) {
 61     return ( ( x >= 0 ) && ( x < n ) && ( y >= 0 ) && ( y < n )  );
 62 }
 63 
 64 void check(int x, int y, int nx, int ny){
 65     if ( ! ( inrange(x,y) && inrange(nx,ny) ) ){
 66     return;
 67     }
 68     if ( map[x][y] == map[nx][ny] ) {
 69     U(x*n+y,nx*n+ny);
 70     }
 71     return;
 72 }
 73 
 74 int flood(){
 75     memset(state,0,sizeof(state));
 76     for ( int i = 0; i < MAXSIZE*MAXSIZE+4; i++ ) {
 77     state[i] = i;
 78     }
 79     for ( int i = 0; i < n; i++ ){
 80     if ( map[0][i] == 'R' ) {
 81         U(UP,i);
 82     }
 83     if ( map[n-1][i] == 'R' ) {
 84         U(DOWN,n*(n-1)+i);
 85     }
 86     if ( map[i][0] == 'B' ) {
 87         U(LEFT,i*n);
 88     }
 89     if ( map[i][n-1] == 'B' ) {
 90         U(RIGHT,i*n+n-1);
 91     }
 92     }
 93     
 94     for ( int i = 0; i < n; i++ ) {
 95     for ( int j = 0; j < n; j++ ) {
 96         if ( map[i][j] != '.' ) {
 97         for ( int k = 0; k < 6; k++ ) {
 98             int nx = i+nextX[k];
 99             int ny = j+nextY[k];
100             check(i,j,nx,ny);
101         }
102         }
103         // for ( int k = 0; k < n*n; k++ ){
104         //if ( k % n == 0 ) cout<<endl;
105         //    cout<<state[k]<<" ";
106         //}
107         //cout<<"~~~~~
";
108     }
109     }
110 }
111 
112 int Bwin(){
113     return F(LEFT) == F(RIGHT);
114 }
115 
116 int Rwin(){
117     return F(UP) == F(DOWN);
118 }
119 
120 int possible(){
121     int t = R-B;
122     int rw = Rwin();
123     int bw = Bwin();
124     t = t > 0? t:-t;
125     // cout<<state[UP]<<" "<<state[LEFT]<<" "<<state[DOWN]<<" "<<state[RIGHT]<<endl;
126     //cout<<rw<<" "<<bw<<" "<<t<<endl;
127     if ( t > 1 ) {
128     return 0;
129     }
130     if ( rw && bw ){
131     return 0;
132     }
133             
134     if ( rw && ( B > R ) ) {
135     return 0;
136     }
137     
138     if ( bw && ( R > B ) ) {
139     return 0;
140     }
141 
142     if ( rw || bw ){
143     int mark = 0;
144     for ( int i = 0; i < n; i++ ) {
145         for ( int j = 0; j < n; j++ ){
146         if ( rw && ( map[i][j] == 'R' ) ){
147             map[i][j] = '.';
148             flood();
149             if ( !Rwin() ){
150             mark ++;
151             }
152             map[i][j] = 'R';
153         }
154         if ( bw && ( map[i][j] == 'B' ) ) {
155             map[i][j] = '.';
156             flood();
157             if ( !Bwin() ){
158             mark ++;
159             }
160             map[i][j] = 'B';
161         }
162         if ( mark != 0 ) return 1;
163         }
164     }
165     if ( mark == 0 ) return 0;
166     }
167 
168     return 1;
169 }    
170 
171 void solve(int x) {
172     input();
173     flood();
174     int rw = Rwin();
175     int bw = Bwin();
176     cout<<"Case #"<<x<<": ";
177     if ( !possible() ) {
178     cout<<"Impossible
";
179     return;
180     }
181     if ( bw ) {
182     cout<<"Blue wins
";
183     return;
184     }
185     if ( rw ) {
186     cout<<"Red wins
";
187     return;
188     }
189     cout<<"Nobody wins
";
190     return;
191 }
192 
193 int main(){
194     int t;
195     cin>>t;
196     for ( int i = 1; i <= t; i++ ) {
197     solve(i);
198     }
199     return 0;
200 }
201 
202

弱的

最后在编码的时候犯了很多很多的错误，很多很多的小细节，最后研究了将近一天，才弄明白怎么回事儿，最后还是那句话，等完全想明白了，再动手。