链接:https://www.nowcoder.com/acm/contest/136/E
来源:牛客网
题目描述
善弈者谋势,不善弈者谋子。
——《弈林新编》
蒟蒻HtBest与神犇WHZ下棋(五子棋),HtBest执黑棋,WHZ执白棋。由于HtBest天资愚笨,不会判断输赢,所以需要你帮他开发一个判断五子棋输赢的程序。
输入描述:
第一行有2个正整数n,m,分别表示棋盘大小(n*n)和对弈步数。
接下来m行,每行两个正整数x
i
,y
i
,表示对弈者下棋的坐标,第2、4、6…行是HtBest下的棋子,第3、5、7…行是WHZ下的棋子。
输出描述:
第一行一个字符串s 和一个正整数num ,用空格隔开,分别表示对弈的胜负结果和该结果出现时的步数,如果HtBest胜则s=“HtBest”,num为HtBest胜利时的步数(为偶数),如果WHZ胜则s=“WHZ”,num为WHZ胜利时的步数(为奇数),如果对弈m步后胜负仍未定,则s=“UNK”,num=m。
提示:当棋盘上第一次有五个子连续排列(横竖斜都可)时,胜负已定。在这之后,两人有可能仍继续落子。
示例1
输入
复制
10 20 1 1 1 2 2 1 2 2 3 1 3 2 4 1 4 2 5 1 5 2 6 1 6 2 7 1 7 2 8 1 8 2 9 1 9 2 10 1 10 2
输出
复制
HtBest 9
说明
在第9步时,HtBest获胜,当前局面:
示例2
输入
复制
10 27 8 6 9 4 2 1 7 5 4 7 8 4 4 3 5 4 10 3 5 5 9 7 9 5 3 4 6 3 5 10 1 5 9 2 6 5 5 7 1 4 2 5 8 5 1 3 3 2 8 3 2 6
输出
复制
WHZ 22
说明
在第22步时,WHZ获胜,当前局面:
示例3
输入
复制
10 1 1 1
输出
复制
UNK 1
说明
下一手后,胜负未分。
备注:
对于100%的测试数据:
1 ≤ n ≤ 1000
1 ≤ m ≤ 100000
发现小白赛后面的题目好水呀。。
这题目比赛的时候竟然没有多少人做。。
卡在前面的题目挺难受的。。
分析:在每次HtBest或者WHZ下棋的时候,判断下他下的这布棋是否可以获胜
获胜的条件,遍历行,列,两种斜线看是否有五个棋子,写几个for循环判断
AC代码:
#include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <vector> #include <string> #include <bitset> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define ls (r<<1) #define rs (r<<1|1) #define debug(a) cout << #a << " " << a << endl using namespace std; typedef long long ll; const ll maxn = 1e6+10; const double eps = 1e-8; const ll mod = 1e9 + 7; const int inf = 0x3f3f3f3f; const double pi = acos(-1.0); ll n, m, mapn[1005][1005]; bool ok( ll x, ll y ) { ll cnt = 1; //下面两个循环判断行是否有五颗棋子 for( ll i = x-1; i >= 1; i -- ) { if( mapn[i][y] == mapn[x][y] ) { cnt ++; } else { break; } if( cnt >= 5 ) { return true; } } for( ll i = x+1; i <= n; i ++ ) { if( mapn[i][y] == mapn[x][y] ) { cnt ++; } else { break; } if( cnt >= 5 ) { return true; } } cnt = 1; //下面两个循环判断列是否有五颗棋子 for( ll i = y-1; i >= 1; i -- ) { if( mapn[x][i] == mapn[x][y] ) { cnt ++; } else { break; } if( cnt >= 5 ) { return true; } } for( ll i = y+1; i <= n; i ++ ) { if( mapn[x][i] == mapn[x][y] ) { cnt ++; } else { break; } if( cnt >= 5 ) { return true; } } cnt = 1; //下面两个循环判断左斜线是否有五颗棋子 for( ll i = x-1, j = y-1; i >= 1 && j >= 1; i --, j -- ) { if( mapn[i][j] == mapn[x][y] ) { cnt ++; } else { break; } if( cnt >= 5 ) { return true; } } for( ll i = x+1, j = y+1; j <= n && i <= n; i ++, j ++ ) { if( mapn[i][j] == mapn[x][y] ) { cnt ++; } else { break; } if( cnt >= 5 ) { return true; } } cnt = 1; //下面两个循环判断右斜线是否有五颗棋子 for( ll i = x-1, j = y+1; i >= 1 && j <= n; i --, j ++ ) { if( mapn[i][j] == mapn[x][y] ) { cnt ++; } else { break; } if( cnt >= 5 ) { return true; } } for( ll i = x+1, j = y-1; i <= n && j >= 1; i ++, j -- ) { if( mapn[i][j] == mapn[x][y] ) { cnt ++; } else { break; } if( cnt >= 5 ) { return true; } } return false; } int main() { ios::sync_with_stdio(0); cin >> n >> m; memset(mapn,0,sizeof(mapn)); bool flag = false; for( ll i = 1, x, y; i <= m; i ++ ) { cin >> x >> y; if(i&1) { mapn[x][y] = 1; } else { mapn[x][y] = 2; } if(!flag) { if(ok(x,y)) { if(i&1) { cout << "HtBest " << i << endl; } else { cout << "WHZ " << i << endl; } flag = true; } } } if(!flag) { cout << "UNK " << m << endl; } return 0; }