https://ac.nowcoder.com/acm/contest/331/B

題解：

std

五子棋只需要計算同方向連續(xù)的五個子即可。

所以對于每次落子，我們只需要知道其4個方向(雙向)連續(xù)的子數(shù)（只需要查找至多4*8個位置是否存在即可）。

需要利用一些簡單的剪枝降低這個查找次數(shù)（比如遇到五子即退出，比如遇到不連續(xù)則continue之類）。

通過以上優(yōu)化，使用set< pair<int,int> >來存放也不會超時。

否則可能需要一定的優(yōu)化才行。

時間復(fù)雜度O(MlogM)O(Mlog?M)（使用平衡樹比如set）或O(M)（如果使用哈希表的話）

#include <bits/stdc++.h> using namespace std;const int mn = 3e5 + 5;const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}; const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};int n; unordered_map<int, bool> h[mn];inline bool inbound(int x, int y) {return x <= n && x >= 1 && y <= n && y >= 1; }inline bool getColor(int x, int y) { return h[x][y]; }inline int getNumberByWay(int k, int x, int y) {int s = 1;while (s <= 5) {int ux = x + dx[k] * s, uy = y + dy[k] * s;if (!inbound(x, y) || !h[ux].count(uy) ||getColor(x, y) != getColor(ux, uy))return s - 1;s++;}return s; }inline bool win(int x, int y, bool color) {h[x][y] = color;for (int i = 0; i < 4; i++) {if (getNumberByWay(i, x, y) + getNumberByWay(i + 4, x, y) + 1 >= 5)return 1;}return 0; }int m;int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int x, y;scanf("%d%d", &x, &y);if (win(x, y, i % 2))puts("Y");elseputs("N");} }

?

總結(jié)

以上是生活随笔為你收集整理的炫酷五子棋的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。