z***9
发帖数: 696 | |
z***9
发帖数: 696 | 2 谁知道这到题 tic-tac-toe：
两个gamer下棋，3X3 board，横线，竖线或对角线上是同一个gamer的棋子win, 问最快
的判断办法？ |
h**k
发帖数: 3368 | 3 一个格子被某个棋手的旗子占据为１，被另外棋手的旗子占据或者空着为０。这样我们
在每次需要判断时，对于每个棋手可以生成一个9 bit的整数。
那么可以建立一个有512元素的数组，每个元素的index对应一个pattern，值则为1，表
示棋手赢；为0，则还没赢。每次判断，直接查询两次数组就可以了。
【在 z***9 的大作中提到】
: 谁知道这到题 tic-tac-toe：
: 两个gamer下棋，3X3 board，横线，竖线或对角线上是同一个gamer的棋子win, 问最快
: 的判断办法？
|
h**k
发帖数: 3368 | 4 我在电面结束快一周的时候发信问recruiter，他才告诉我说电面通过了，已经准备安
排onsite。所以不要急。你可以先在就发信或者打电话给联系你的recruiter，问问情
况。
【在 z***9 的大作中提到】
: 多半要被拒了，咳。。。
|
h**6
发帖数: 4160 | 5 DP
每个格子有三种情况，总共3^9种布局。
任何一种布局可能有先胜，后胜，未分出胜负，无效(双方都三连或先后手棋子数差不
为0或1)
从满局往空局方向开始判断，每种布局最多有9种发展，对对手最有利的结果是该布局
的结果。
因此复杂度为3^9*9 = 177147
【在 z***9 的大作中提到】
: 谁知道这到题 tic-tac-toe：
: 两个gamer下棋，3X3 board，横线，竖线或对角线上是同一个gamer的棋子win, 问最快
: 的判断办法？
|
z***9
发帖数: 696 | 6 这个办法如果是10x10就不好解决吧，只写了个用循环判断的办法，别要求改进，但是
说不出来。。。
【在 h**k 的大作中提到】
: 一个格子被某个棋手的旗子占据为１，被另外棋手的旗子占据或者空着为０。这样我们
: 在每次需要判断时，对于每个棋手可以生成一个9 bit的整数。
: 那么可以建立一个有512元素的数组，每个元素的index对应一个pattern，值则为1，表
: 示棋手赢；为0，则还没赢。每次判断，直接查询两次数组就可以了。
|
v***n
发帖数: 5085 | |
h**k
发帖数: 3368 | 8 你循环判断是指对所有赢的可能组合进行判断？三列，三行，两个对角？
比如对第一行，判断写的是a[1]==1 && a[2] == 1 && a[3] == 1？
如果是这样的话，可以考虑用bit operation，用mark来判断。
比如对于第一行，mark 为111000000，&之后如果等于mark，就判断赢了。
【在 z***9 的大作中提到】
: 这个办法如果是10x10就不好解决吧，只写了个用循环判断的办法，别要求改进，但是
: 说不出来。。。
|
