One day, Alice asks Bob to play a game called “K-in-a-row”. There is a game board whose size is N*M. Alice plays first, and they alternate in placing a piece of their color on an empty intersection. The winner is the first player to get an unbroken row of K stones horizontally, vertically, or diagonally. Now given the last situation of the game board, I would like to know who win or just a draw?
输入
The first line of input is the number of test cases T.
For each test case. The first line contains three integers N(3<= N <=15), M(3<=M<=15) and K(3<=K<=6).The next N line, each line contains M pieces, ‘A’ means Alice’s place and ‘B’ means Bob’s place while ‘O’ means empty. It is promised that at most one player wins.
输出
For each test case output the answer on a single line, if Alice wins then print “Alice Win!”, if Bob wins then print ”Bob Win!”, if no one wins, then print ”No Win!”.
样例输入
2 6 6 6 AOOOOO BABBOO OOAOBO OOOAOO OOBOAO OOOOOA 5 5 3 AOBOA BABAO OOBOO OOOOO OOOOO
样例输出
Alice Win! Bob Win!
思路：就是个五子棋，DFS即可。但是我的代码没有A，找不到问题。所以附上我的代码和正确代码。
我的代码：
// Alice and Bob_K_win.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" //备注：没有AC！ #include <iostream> #include <cstring> using namespace std; const int MAX = 20; int t, n, m, k,ans, vis[MAX][MAX],dir[8][2] = { 1, 0, -1, 0, 0, 1, 0, -1, 1, 1, -1, -1, 1, -1, -1, 1 }; char map[MAX][MAX]; void DFS(int x, int y,int a,int b) { //cout << "x:" << x << " y:" << y << " a:" << a << " b:" << b << endl; if (ans != 0) return; if (a == k || b == k) { if (a == k) ans = 1; else ans = 2; return; } for (int i = 0; i < 8; i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && map[nx][ny] != 'O') { //cout << "nx:" << nx << " ny:" << ny << " map[nx][ny]:" << map[nx][ny] << endl; vis[nx][ny] = 1; if (map[nx][ny] == 'A') DFS(nx, ny, a + 1, b); else DFS(nx, ny, a, b + 1); } } } int main() { cin >> t; while (t--) { memset(vis, 0, sizeof(vis)); memset(map, ' ', sizeof(map)); ans = 0; cin >> n >> m >> k; for (int i = 0; i < n; i++) cin >> map[i]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] != 'O' && !vis[i][j]) { vis[i][j] = 1; if (map[i][j] == 'A') DFS(i, j, 1, 0); else if (map[i][j] == 'B') DFS(i, j, 0, 1); } } } if (ans == 1) cout << "Alice Win!" << endl; else if (ans == 2) cout << "Bob Win!" << endl; else cout << "No Win!" << endl; } }
正确的代码：
#include<cstdio> #include<iostream> using namespace std; int n,m,k,flag; char map[20][20]; void dfs(int x,int y,int num,int dis,char e) { if(num>k) { flag=1; if(e=='A') cout<<"Alice Win!"<<endl; else cout<<"Bob Win!"<<endl; return ; } if(map[x][y]==e && x<n && x>=0 && y<m && y>=0) { switch(dis) { case 1: dfs(x,y+1,num+1,dis,e);break; case 2: dfs(x,y-1,num+1,dis,e);break; case 3: dfs(x+1,y,num+1,dis,e);break; case 4: dfs(x-1,y,num+1,dis,e);break; case 5: dfs(x+1,y+1,num+1,dis,e);break; case 6: dfs(x+1,y-1,num+1,dis,e);break; case 7: dfs(x-1,y-1,num+1,dis,e);break; case 8: dfs(x-1,y+1,num+1,dis,e);break; } } } void solve() { flag=0; for(int i=0;i<n;i++)//A { for(int j=0;j<m;j++) { if(map[i][j]=='A') { for(int k=1;k<=8;k++) dfs(i,j,1,k,'A'); } if(flag) break; } if(flag) break; } if(!flag) { for(int i=0;i<n;i++)//B { for(int j=0;j<m;j++) { if(map[i][j]=='B') { for(int k=1;k<=8;k++) dfs(i,j,1,k,'B'); } if(flag) break; } if(flag) break; } } if(!flag) cout<<"No Win!"<<endl; } int main() { int t; cin>>t; while(t--) { cin>>n>>m>>k; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) cin>>map[i][j]; } solve(); } return 0; }