題干：
?

五子棋是一個簡單的雙人游戲。

小希最近在思索一種更好玩的五子棋。她希望勝利不再是誰先五子連珠誰贏，而變成誰落子后，該子與之前的子五子連珠的次數(shù)更多才能勝利。

但是如果是在普通的棋盤上，這個游戲又顯得不是很有趣，所以她將棋盤擴(kuò)大至N*N，因?yàn)槠灞P過大，沒有一個程序能將其展示出來，所以如何落子只能憑借記憶。

她希望你能寫一個程序，判斷每步落子與之前的同色棋子是否能形成五子連珠。
?

五子連珠是指是橫著豎著或者斜著的八個方向存在連續(xù)的顏色相同的至少五個子。

?

注意：這個版本的五子棋仍然是雙人游戲，先手執(zhí)黑，后手執(zhí)白。同色才是五子棋。

輸入描述:

第一行一個正整數(shù)N,M，表示棋盤大小和落子次數(shù)。 隨后M行，每行兩個整數(shù)xixi,yiyi，表示落子位置。N,M≤300,000N,M≤300,000 1≤xi,yi≤N1≤xi,yi≤N數(shù)據(jù)保證同一個子的位置不會多次落子。

輸出描述:

對于每一個子，一行，如果該步落下后，該子和其他子能形成五子連珠，輸出一個大寫的'Y'，否則輸出一個大寫的'N'。

示例1

輸入

復(fù)制

6 12 1 1 6 1 2 2 5 2 3 3 4 3 4 4 3 4 5 5 2 5 6 6 1 6

輸出

復(fù)制

N N N N N N N N Y Y Y Y

解題報(bào)告：

? ?這題卡常數(shù)太狠了啊、、、set判斷邊界是否出現(xiàn)過，，，隨便怎么寫來標(biāo)記這個二維坐標(biāo)，都可以。（如果這個棋盤說了n*m<1e6，，甚至可以用二維vector，但是這里是n*n，就沒治了）

AC代碼1：

#include<bits/stdc++.h> using namespace std; struct Node {int x, y;Node(int x, int y) : x(x), y(y) {}bool operator < (const Node& node) const {return x < node.x || (x == node.x && y < node.y);} }; int n, m; set<Node> st[2]; const int dx[] = {0, 1, 1, 1}; const int dy[] = {1, 0, 1, -1}; bool judge(int x, int y, int c) {for(int k = 0; k < 4; k++) {int cnt = 1;for(int i = 1; i <= 4; i++) {Node tmp(x+i*dx[k], y+i*dy[k]);if(st[c].find(tmp) == st[c].end())break;cnt++;}for(int i = 1; i <= 4; i++) {Node tmp(x-i*dx[k], y-i*dy[k]);if(st[c].find(tmp) == st[c].end())break;cnt++;}if(cnt >= 5) return true;}return false; } int main() {cin>>n>>m;for(int i = 0; i < m; i++) {int x, y; scanf("%d%d",&x,&y);st[i&1].insert(Node(x, y));puts(judge(x, y, i&1) ? "Y" : "N");}return 0; }

AC標(biāo)程：（但是因?yàn)閿?shù)據(jù)問題，這題不加判邊界這一句，也可以AC）

#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");} }

AC代碼2：（Hash版本）

#include<bits/stdc++.h> #define ll long long using namespace std; int ha[10000007]={0}; int n,m,x,y; const ll mod = 9989783; ll seed = 3e5 + 7; inline int read(){int x = 0;char c = getchar();while(c<'0'||c>'9') c = getchar();while(c>='0'&&c<='9'){x = x*10 + c-'0';c = getchar();}return x; } inline int gethash(ll x,ll y){int t = (x*seed + y)%mod;return t; } int find(int x,int y,int dx,int dy,int p,int d){if(d>=4) return d;if(x>=1&&x<=n&&y>=1&&y<=n&&ha[gethash(x,y)] == p) return find(x+dx,y+dy,dx,dy,p,d+1);return d; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;++i){x = read();y = read();ha[gethash(x,y)] = i%2 + 1;if(find(x-1,y-1,-1,-1,i%2 + 1,0) + find(x+1,y+1,1,1,i%2 + 1,0)>=4|| find(x-1,y+1,-1,1,i%2 + 1,0) + find(x+1,y-1,1,-1,i%2 + 1,0)>=4|| find(x-1,y,-1,0,i%2 + 1,0) + find(x+1,y,1,0,i%2 + 1,0)>=4|| find(x,y-1,0,-1,i%2 + 1,0) + find(x,y+1,0,1,i%2 + 1,0)>=4) printf("Y\n");else printf("N\n");} }

AC代碼3：（900ms）

#include<bits/stdc++.h> using namespace std; struct Node {int x, y;Node(int x, int y) : x(x), y(y) {}bool operator < (const Node& node) const {return x < node.x || (x == node.x && y < node.y);} }; int n, m; set<Node> st[2]; const int dx[] = {0, 1, 1, 1}; const int dy[] = {1, 0, 1, -1}; bool judge(int x, int y, int c) {for(int k = 0; k < 4; k++) {int cnt = 1;for(int i = 1; i <= 4; i++) {Node tmp(x+i*dx[k], y+i*dy[k]);if(st[c].find(tmp) == st[c].end())break;cnt++;}for(int i = 1; i <= 4; i++) {Node tmp(x-i*dx[k], y-i*dy[k]);if(st[c].find(tmp) == st[c].end())break;cnt++;}if(cnt >= 5) return true;}return false; } int main() {cin>>n>>m;for(int i = 0; i < m; i++) {int x, y; scanf("%d%d",&x,&y);st[i&1].insert(Node(x, y));puts(judge(x, y, i&1) ? "Y" : "N");}return 0; }

?

但是這套代碼你要是judge函數(shù)這么寫就必須用個Hash來寫，不然就會T，，不知道為啥。（1600ms左右）

雖然判邊界沒用但是這題還是有點(diǎn)用的，，因?yàn)橐磎p是否越界、、但是上面那個代碼不加這個判斷邊界這個函數(shù)也可以AC，，我感覺就是因?yàn)榉较虻捻樞騿栴}吧、

#include<bits/stdc++.h> using namespace std; struct Node {int x, y;Node(int x, int y) : x(x), y(y) {}bool operator < (const Node& node) const {return x < node.x || (x == node.x && y < node.y);} }; int n, m; set<Node> st[2]; unordered_map<int , bool > mp[300005]; const int dx[] = {0, 1, 1, 1}; const int dy[] = {1, 0, 1, -1}; inline bool inbound(int x, int y) {return x <= n && x >= 1 && y <= n && y >= 1; } bool judge(int x, int y, int c) {for(int k = 0; k < 4; k++) {int cnt = 0;for(int i = -4; i <= 4; i++) {int tx = x+i*dx[k];int ty = y+i*dy[k];if(!inbound(tx,ty) || !mp[tx].count(ty) || mp[tx][ty] != mp[x][y]) {cnt = 0;continue;}if(++cnt >= 5) return true;}}return false;} int main() {cin>>n>>m;for(int i = 0; i < m; i++) {int x, y;scanf("%d%d",&x,&y);mp[x][y]=i%2;//puts(judge(x, y, i%2) ? "Y" : "N");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 331B】炫酷五子棋（STLset 或Hash，tricks，二维map标记）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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