怎么修复网站死链,建设集团有限公司英文,枣阳网站建设_枣阳山水数码,网站开发还找到工作吗五子棋对弈
问题描述
“在五子棋的对弈中#xff0c;友谊的小船说翻就翻#xff1f;” 不#xff01;对小蓝和小桥来说#xff0c;五子棋不仅是棋盘上的较量#xff0c;更是心与心之间的沟通。这两位挚友秉承着友谊第一#xff0c;比赛第二的宗旨#xff…五子棋对弈
问题描述
“在五子棋的对弈中友谊的小船说翻就翻” 不对小蓝和小桥来说五子棋不仅是棋盘上的较量更是心与心之间的沟通。这两位挚友秉承着友谊第一比赛第二的宗旨决定在一块 5×5 的棋盘上用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落于是决定用一场和棋平局作为彼此友谊的见证。
比赛遵循以下规则
棋盘规模比赛在一个 5×5 的方格棋盘上进行共有 25 个格子供下棋使用。棋子类型两种棋子黑棋与白棋代表双方。小蓝持白棋小桥持黑棋。先手规则白棋小蓝具有先手优势即在棋盘空白时率先落子下棋。轮流落子玩家们交替在棋盘上放置各自的棋子每次仅放置一枚。胜利条件率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。平局条件当所有 25 个棋盘格都被下满棋子而未决出胜负时游戏以平局告终。
在这一设定下小蓝和小桥想知道有多少种不同的棋局情况既确保棋盘下满又保证比赛结果为平局。
答案提交
这是一道结果填空题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
c代码
#includebits/stdc.husing namespace std;class check {
public:int cur;int left;int up;int slash;int slash_fu;
};int white 0, black 0;
check chess[5][5];
int ans 0;void dfs(int i, int j, int cur) {chess[i][j].left 1;chess[i][j].up 1;chess[i][j].slash 1;chess[i][j].slash_fu 1;if (j 1 cur chess[i][j - 1].cur) {if (chess[i][j - 1].left 4) return;chess[i][j].left chess[i][j - 1].left 1;}if (i 1 cur chess[i - 1][j].cur) {if (chess[i - 1][j].up 4) return;chess[i][j].up chess[i - 1][j].up 1;}if (i 1 j 1 cur chess[i - 1][j - 1].cur) {if (chess[i - 1][j - 1].slash 4) return;chess[i][j].slash chess[i - 1][j - 1].slash 1;}if (i 1 j 1 4 cur chess[i - 1][j 1].cur) {if (chess[i - 1][j 1].slash_fu 4) return;chess[i][j].slash_fu chess[i - 1][j 1].slash_fu 1;}chess[i][j].cur cur;if (i 4 j 4) {ans;return;}int x, y;x i;y j 1;if (j 4) {x i 1;y 0;}if (white 13) {white;dfs(x, y, 0);white--;}if (black 12) {black;dfs(x, y, 1);black--;}
}int main() {/*white;dfs(0, 0, 0);white--;black;dfs(0, 0, 1);black--;cout ans;*/cout 3126376;return 0;
}//by wqs题目解析
该问题是一个dfs深度搜索问题不过要剪枝。
因为从左往右从上往下填所以可以不用考虑棋盘右边和下面的情况。
如果左边有四个和当前颜色相同直接return;
如果上边有四个和当前颜色相同直接return;
如果主对角线斜向上有四个和当前颜色相同直接return;
如果副对角线斜向上有四个和当前颜色相同直接return;
我当时还不记得考虑副对角线了不知道算不算坑。
另外白子13个黑子12个要判断黑子、白子数量是否大于0再考虑下什么棋子。
代码实现
check类
class check {
public:int cur; //当前棋子的颜色0表示白棋1表示黑棋int left;//左边棋子连珠个数(连珠个数指的是连续颜色相同的棋子数量包含自己)int up;//上边棋子连珠个数int slash;//主对角线棋子连珠个数int slash_fu;//副对角线棋子连珠个数
};
check chess[5][5];//模拟棋盘真实情况
//如果chess[i][j].cur chess[i][j - 1].cur,chess[i][j].left chess[i][j - 1].left 1;
//如果我填入的这个棋子m的颜色和左边棋子n的颜色相同,m的左边棋子连珠数量n的左边棋子连珠数量1;
//如果chess[i][j].cur ! chess[i][j - 1].cur,chess[i][j].left 1;
//如果我填入的这个棋子m的颜色和左边棋子n的颜色不相同,m的左边棋子连珠数量1;
//其他位置的动态转移方程自行推导。dfs深度搜索
//在chess[i][j]填入cur
void dfs(int i, int j, int cur) {chess[i][j].left 1;//初始化chess[i][j].up 1;chess[i][j].slash 1;chess[i][j].slash_fu 1;if (j 1 cur chess[i][j - 1].cur) {if (chess[i][j - 1].left 4) return;//如果左边有四个和当前颜色相同直接return;chess[i][j].left chess[i][j - 1].left 1;}//检查左边if (i 1 cur chess[i - 1][j].cur) {if (chess[i - 1][j].up 4) return;//如果上边有四个和当前颜色相同直接return;chess[i][j].up chess[i - 1][j].up 1;}//检查上面if (i 1 j 1 cur chess[i - 1][j - 1].cur) {if (chess[i - 1][j - 1].slash 4) return;//如果主对角线斜向上有四个和当前颜色相同直接return;chess[i][j].slash chess[i - 1][j - 1].slash 1;}//检查主对角线if (i 1 j 1 4 cur chess[i - 1][j 1].cur) {if (chess[i - 1][j 1].slash_fu 4) return;//如果副对角线斜向上有四个和当前颜色相同直接return;chess[i][j].slash_fu chess[i - 1][j 1].slash_fu 1;}//检查副对角线chess[i][j].cur cur;//说明可以填入if (i 4 j 4) {//说明棋盘填完了ans;return;}int x, y;x i;y j 1;//往右走if (j 4) {x i 1;y 0;//往下走}if (white 13) {white;dfs(x, y, 0);//下一个格子填白色white--;}if (black 12) {black;dfs(x, y, 1);//下一个格子填黑色black--;}
}ans就是我们的答案
