五子棋判断 五子连珠

题目链接：/acm/contest/331/B

题目大意：

思路：因为N太大。二维数组肯定是开不下。所以用map存就可以了。

当时就去写了二百多行的代码，太暴力了。把五子棋所有可能形成五子连珠的情况都写出来的。

后来看了一些大佬的写法，找了简单的方法遍历五子棋的棋盘：

#include<bits/stdc++.h>using namespace std;typedef long long ll;#define p1 first#define p2 second//memset(a, 0, sizeof(a));//stack堆栈 queue队列 priority_queue优先队列//vector向量 multiset平衡二叉树 deque双端队列//pair{T1 first;T2 second;} greater<T>//unordered_map 哈希mapunordered_map<int, int> e[300005];int dis[2][8]={-1, 1, 0, 0, 1, -1, -1, 1,-1, 1, 1,-1, 0, 0, 1,-1};int n, m, x, y;int dfs(int x, int y, int z){z=(z%2)?1:2;for(int i=0;i<8;i+=2){int a=0, b=0; //左侧与右侧的棋子数量int xx=x+dis[0][i], yy=y+dis[1][i];while(xx>=1&&xx<=n&&yy>=1&&yy<=n&&e[xx][yy]==z){a++, xx+=dis[0][i], yy+=dis[1][i];}xx=x+dis[0][i+1], yy=y+dis[1][i+1];while(xx>=1&&xx<=n&&yy>=1&&yy<=n&&e[xx][yy]==z){b++, xx+=dis[0][i+1], yy+=dis[1][i+1];}if(a+b>=4)//>=4满足五子棋{return 1;}}return 0;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);printf("%c\n",(dfs(x, y, i))==1?'Y':'N');e[x][y]=(i%2)?1:2;}return 0;}

原来的代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;#define p1 first#define p2 second//memset(a, 0, sizeof(a));//stack堆栈 queue队列 priority_queue优先队列//vector向量 multiset平衡二叉树 deque双端队列//pair{T1 first;T2 second;} greater<T>//unordered_map 哈希mapmultimap<pair<int, int>, int> s1;multimap<pair<int, int>, int> s2;int dfs1(int x, int y){if(s1.find(make_pair(x, y-1))!=s1.end()&&s1.find(make_pair(x, y-2))!=s1.end()&&s1.find(make_pair(x, y-3))!=s1.end()&&s1.find(make_pair(x, y-4))!=s1.end()){return 1;}if(s1.find(make_pair(x, y-1))!=s1.end()&&s1.find(make_pair(x, y-2))!=s1.end()&&s1.find(make_pair(x, y-3))!=s1.end()&&s1.find(make_pair(x, y+1))!=s1.end()){return 1;}if(s1.find(make_pair(x, y-1))!=s1.end()&&s1.find(make_pair(x, y-2))!=s1.end()&&s1.find(make_pair(x, y+2))!=s1.end()&&s1.find(make_pair(x, y+1))!=s1.end()){return 1;}if(s1.find(make_pair(x, y-1))!=s1.end()&&s1.find(make_pair(x, y+3))!=s1.end()&&s1.find(make_pair(x, y+2))!=s1.end()&&s1.find(make_pair(x, y+1))!=s1.end()){return 1;}if(s1.find(make_pair(x, y+4))!=s1.end()&&s1.find(make_pair(x, y+3))!=s1.end()&&s1.find(make_pair(x, y+2))!=s1.end()&&s1.find(make_pair(x, y+1))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y))!=s1.end()&&s1.find(make_pair(x-2, y))!=s1.end()&&s1.find(make_pair(x-3, y))!=s1.end()&&s1.find(make_pair(x-4, y))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y))!=s1.end()&&s1.find(make_pair(x-2, y))!=s1.end()&&s1.find(make_pair(x-3, y))!=s1.end()&&s1.find(make_pair(x+1, y))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y))!=s1.end()&&s1.find(make_pair(x-2, y))!=s1.end()&&s1.find(make_pair(x+2, y))!=s1.end()&&s1.find(make_pair(x+1, y))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y))!=s1.end()&&s1.find(make_pair(x+3, y))!=s1.end()&&s1.find(make_pair(x+2, y))!=s1.end()&&s1.find(make_pair(x+1, y))!=s1.end()){return 1;}if(s1.find(make_pair(x+4, y))!=s1.end()&&s1.find(make_pair(x+3, y))!=s1.end()&&s1.find(make_pair(x+2, y))!=s1.end()&&s1.find(make_pair(x+1, y))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y-1))!=s1.end()&&s1.find(make_pair(x-2, y-2))!=s1.end()&&s1.find(make_pair(x-3, y-3))!=s1.end()&&s1.find(make_pair(x-4, y-4))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y-1))!=s1.end()&&s1.find(make_pair(x-2, y-2))!=s1.end()&&s1.find(make_pair(x-3, y-3))!=s1.end()&&s1.find(make_pair(x+1, y+1))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y-1))!=s1.end()&&s1.find(make_pair(x-2, y-2))!=s1.end()&&s1.find(make_pair(x+2, y+2))!=s1.end()&&s1.find(make_pair(x+1, y+1))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y-1))!=s1.end()&&s1.find(make_pair(x+3, y+3))!=s1.end()&&s1.find(make_pair(x+2, y+2))!=s1.end()&&s1.find(make_pair(x+1, y+1))!=s1.end()){return 1;}if(s1.find(make_pair(x+4, y+4))!=s1.end()&&s1.find(make_pair(x+3, y+3))!=s1.end()&&s1.find(make_pair(x+2, y+2))!=s1.end()&&s1.find(make_pair(x+1, y+1))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y+1))!=s1.end()&&s1.find(make_pair(x-2, y+2))!=s1.end()&&s1.find(make_pair(x-3, y+3))!=s1.end()&&s1.find(make_pair(x-4, y+4))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y+1))!=s1.end()&&s1.find(make_pair(x-2, y+2))!=s1.end()&&s1.find(make_pair(x-3, y+3))!=s1.end()&&s1.find(make_pair(x+1, y-1))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y+1))!=s1.end()&&s1.find(make_pair(x-2, y+2))!=s1.end()&&s1.find(make_pair(x+2, y-2))!=s1.end()&&s1.find(make_pair(x+1, y-1))!=s1.end()){return 1;}if(s1.find(make_pair(x-1, y+1))!=s1.end()&&s1.find(make_pair(x+3, y-3))!=s1.end()&&s1.find(make_pair(x+2, y-2))!=s1.end()&&s1.find(make_pair(x+1, y-1))!=s1.end()){return 1;}if(s1.find(make_pair(x+4, y-4))!=s1.end()&&s1.find(make_pair(x+3, y-3))!=s1.end()&&s1.find(make_pair(x+2, y-2))!=s1.end()&&s1.find(make_pair(x+1, y-1))!=s1.end()){return 1;}return 0;}int dfs2(int x, int y){if(s2.find(make_pair(x, y-1))!=s2.end()&&s2.find(make_pair(x, y-2))!=s2.end()&&s2.find(make_pair(x, y-3))!=s2.end()&&s2.find(make_pair(x, y-4))!=s2.end()){return 1;}if(s2.find(make_pair(x, y-1))!=s2.end()&&s2.find(make_pair(x, y-2))!=s2.end()&&s2.find(make_pair(x, y-3))!=s2.end()&&s2.find(make_pair(x, y+1))!=s2.end()){return 1;}if(s2.find(make_pair(x, y-1))!=s2.end()&&s2.find(make_pair(x, y-2))!=s2.end()&&s2.find(make_pair(x, y+2))!=s2.end()&&s2.find(make_pair(x, y+1))!=s2.end()){return 1;}if(s2.find(make_pair(x, y-1))!=s2.end()&&s2.find(make_pair(x, y+3))!=s2.end()&&s2.find(make_pair(x, y+2))!=s2.end()&&s2.find(make_pair(x, y+1))!=s2.end()){return 1;}if(s2.find(make_pair(x, y+4))!=s2.end()&&s2.find(make_pair(x, y+3))!=s2.end()&&s2.find(make_pair(x, y+2))!=s2.end()&&s2.find(make_pair(x, y+1))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y))!=s2.end()&&s2.find(make_pair(x-2, y))!=s2.end()&&s2.find(make_pair(x-3, y))!=s2.end()&&s2.find(make_pair(x-4, y))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y))!=s2.end()&&s2.find(make_pair(x-2, y))!=s2.end()&&s2.find(make_pair(x-3, y))!=s2.end()&&s2.find(make_pair(x+1, y))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y))!=s2.end()&&s2.find(make_pair(x-2, y))!=s2.end()&&s2.find(make_pair(x+2, y))!=s2.end()&&s2.find(make_pair(x+1, y))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y))!=s2.end()&&s2.find(make_pair(x+3, y))!=s2.end()&&s2.find(make_pair(x+2, y))!=s2.end()&&s2.find(make_pair(x+1, y))!=s2.end()){return 1;}if(s2.find(make_pair(x+4, y))!=s2.end()&&s2.find(make_pair(x+3, y))!=s2.end()&&s2.find(make_pair(x+2, y))!=s2.end()&&s2.find(make_pair(x+1, y))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y-1))!=s2.end()&&s2.find(make_pair(x-2, y-2))!=s2.end()&&s2.find(make_pair(x-3, y-3))!=s2.end()&&s2.find(make_pair(x-4, y-4))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y-1))!=s2.end()&&s2.find(make_pair(x-2, y-2))!=s2.end()&&s2.find(make_pair(x-3, y-3))!=s2.end()&&s2.find(make_pair(x+1, y+1))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y-1))!=s2.end()&&s2.find(make_pair(x-2, y-2))!=s2.end()&&s2.find(make_pair(x+2, y+2))!=s2.end()&&s2.find(make_pair(x+1, y+1))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y-1))!=s2.end()&&s2.find(make_pair(x+3, y+3))!=s2.end()&&s2.find(make_pair(x+2, y+2))!=s2.end()&&s2.find(make_pair(x+1, y+1))!=s2.end()){return 1;}if(s2.find(make_pair(x+4, y+4))!=s2.end()&&s2.find(make_pair(x+3, y+3))!=s2.end()&&s2.find(make_pair(x+2, y+2))!=s2.end()&&s2.find(make_pair(x+1, y+1))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y+1))!=s2.end()&&s2.find(make_pair(x-2, y+2))!=s2.end()&&s2.find(make_pair(x-3, y+3))!=s2.end()&&s2.find(make_pair(x-4, y+4))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y+1))!=s2.end()&&s2.find(make_pair(x-2, y+2))!=s2.end()&&s2.find(make_pair(x-3, y+3))!=s2.end()&&s2.find(make_pair(x+1, y-1))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y+1))!=s2.end()&&s2.find(make_pair(x-2, y+2))!=s2.end()&&s2.find(make_pair(x+2, y-2))!=s2.end()&&s2.find(make_pair(x+1, y-1))!=s2.end()){return 1;}if(s2.find(make_pair(x-1, y+1))!=s2.end()&&s2.find(make_pair(x+3, y-3))!=s2.end()&&s2.find(make_pair(x+2, y-2))!=s2.end()&&s2.find(make_pair(x+1, y-1))!=s2.end()){return 1;}if(s2.find(make_pair(x+4, y-4))!=s2.end()&&s2.find(make_pair(x+3, y-3))!=s2.end()&&s2.find(make_pair(x+2, y-2))!=s2.end()&&s2.find(make_pair(x+1, y-1))!=s2.end()){return 1;}return 0;}int main(){int n, m, x, y;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);if(i%2==1){if(dfs1(x, y)){printf("Y\n");s1.insert(make_pair(make_pair(x, y), 1));}else{printf("N\n");s1.insert(make_pair(make_pair(x, y), 1));}}else{if(dfs2(x, y)){printf("Y\n");s2.insert(make_pair(make_pair(x, y), 1));}else{printf("N\n");s2.insert(make_pair(make_pair(x, y), 1));}}}return 0;}