公益平台网站怎么做,销售新人怎么找客户,深圳网站制作公司讯息,婚纱网站设计素材题干#xff1a;
五子棋是一个简单的双人游戏。 小希最近在思索一种更好玩的五子棋。她希望胜利不再是谁先五子连珠谁赢#xff0c;而变成谁落子后#xff0c;该子与之前的子五子连珠的次数更多才能胜利。 但是如果是在普通的棋盘上#xff0c;这个游戏又显得不是很有趣…题干
五子棋是一个简单的双人游戏。 小希最近在思索一种更好玩的五子棋。她希望胜利不再是谁先五子连珠谁赢而变成谁落子后该子与之前的子五子连珠的次数更多才能胜利。 但是如果是在普通的棋盘上这个游戏又显得不是很有趣所以她将棋盘扩大至N*N因为棋盘过大没有一个程序能将其展示出来所以如何落子只能凭借记忆。 她希望你能写一个程序判断每步落子与之前的同色棋子是否能形成五子连珠。
五子连珠是指是横着竖着或者斜着的八个方向存在连续的颜色相同的至少五个子。 注意这个版本的五子棋仍然是双人游戏先手执黑后手执白。同色才是五子棋。
输入描述:
第一行一个正整数N,M表示棋盘大小和落子次数。
随后M行每行两个整数xixi,yiyi表示落子位置。N,M≤300,000N,M≤300,000
1≤xi,yi≤N1≤xi,yi≤N数据保证同一个子的位置不会多次落子。
输出描述:
对于每一个子一行如果该步落下后该子和其他子能形成五子连珠输出一个大写的Y否则输出一个大写的N。
示例1
输入
复制
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
输出
复制
N
N
N
N
N
N
N
N
Y
Y
Y
Y
解题报告 这题卡常数太狠了啊、、、set判断边界是否出现过随便怎么写来标记这个二维坐标都可以。如果这个棋盘说了n*m1e6甚至可以用二维vector但是这里是n*n就没治了
AC代码1
#includebits/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;
setNode 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(xi*dx[k], yi*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() {cinnm;for(int i 0; i m; i) {int x, y; scanf(%d%d,x,y);st[i1].insert(Node(x, y));puts(judge(x, y, i1) ? Y : N);}return 0;
}
AC标程但是因为数据问题这题不加判边界这一句也可以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_mapint, 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代码2Hash版本
#includebits/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(c0||c9) c getchar();while(c0c9){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(d4) return d;if(x1xny1ynha[gethash(x,y)] p) return find(xdx,ydy,dx,dy,p,d1);return d;
}
int main(){scanf(%d%d,n,m);for(int i1;im;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(x1,y1,1,1,i%2 1,0)4|| find(x-1,y1,-1,1,i%2 1,0) find(x1,y-1,1,-1,i%2 1,0)4|| find(x-1,y,-1,0,i%2 1,0) find(x1,y,1,0,i%2 1,0)4|| find(x,y-1,0,-1,i%2 1,0) find(x,y1,0,1,i%2 1,0)4) printf(Y\n);else printf(N\n);}
}
AC代码3900ms
#includebits/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;
setNode 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(xi*dx[k], yi*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() {cinnm;for(int i 0; i m; i) {int x, y; scanf(%d%d,x,y);st[i1].insert(Node(x, y));puts(judge(x, y, i1) ? Y : N);}return 0;
} 但是这套代码你要是judge函数这么写就必须用个Hash来写不然就会T不知道为啥。1600ms左右
虽然判边界没用但是这题还是有点用的因为要看mp是否越界、、但是上面那个代码不加这个判断边界这个函数也可以AC我感觉就是因为方向的顺序问题吧、
#includebits/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;
setNode st[2];
unordered_mapint , 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 xi*dx[k];int ty yi*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() {cinnm;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;
}
