棋盘覆盖问题的算法实现

发布网友发布时间：2022-04-23 03:37

共2个回答

懂视网时间：2022-04-23 07:58

这次给大家带来JS实现棋盘覆盖，JS实现棋盘覆盖的注意事项有哪些，下面就是实战案例，一起来看一下。

之前做了一个算法作业，叫做棋盘覆盖，本来需要用c语言来编写的，但是因为我的c语言是半桶水（哈哈），所以索性就把网上的c语言写法改成JavaScript写法，并且把它的覆盖效果显示出来

<!DOCTYPE html>
<html>
<head><meta http-equiv="Content-Type"content="text/html; charset=utf-8"/>
<title>算法作业2</title>
<style type="text/css">
 #num{}
 #chess{
 margin-top:20px;
 }
</style>
</head>
<body>
 <p id="num">
 <p>设置棋盘大小：
 <input type="text"name="Num"size="4"/>
 </p>
 <p>请输入特殊方格的位置：</p>
 <p>
 x:<input type="text"name="X"size="25"/><br />
 y:<input type="text"name="Y"size="25"/>
 </p>
 <p>
 <input type="button"value="设置棋盘参数"/>
 <input type="button"value="生成棋盘"/>
 </p>
 </p>
 <p id="chess">
 </p>
</body>
</html>
<script type="text/javascript">
 window.onload=function()
 {//棋盘设置
 varchess=document.getElementById('chess');
 varinput=document.getElementsByTagName('input')[3];
 input.onclick=function()
 {
 varN=document.getElementsByTagName('input')[0].value;
 vartable=document.createElement('table');
 chess.appendChild(table);
 table.style.border='2px solid';
 table.style.borderCollapse='collapse';
 for(vari=0;i<N;i++)
 {
 vartr=document.createElement('tr');
 table.appendChild(tr);
 tr.style.height ="20px";
 tr.style.border='1px solid #ccc';
 for(varj=0;j<N;j++)
 {
  vartd=document.createElement('td');
  tr.appendChild(td);
  td.style.width ="20px";
  td.style.border='1px solid #ccc';
 }
 } 
 }
 varOut=document.getElementsByTagName('input')[4];
 varMatrix =newArray(); 
 for(vari=0;i<100; i++)
 {//初始化棋盘矩阵
 Matrix[i] =newArray(); 
 for(varj=0;j<100;j++)
 {
  Matrix[i][j]=0;
 }
 }
 Out.onclick=function()
 {//棋盘生成
 varr,c;
 varX=document.getElementsByTagName('input')[1].value;
 varY=document.getElementsByTagName('input')[2].value;
 varN=document.getElementsByTagName('input')[0].value;
 chessBoard(0,0,X-1,Y-1,N);
 for(r = 0; r < N; r++)
 {
 for(c = 0; c < N; c++)
 {
  varq=Matrix[r][c];
  vartable=document.getElementsByTagName('table')[0];
  table.rows[r].cells[c].style.background='rgb('+13*q%256+','+43*q%256+','+73*q%256+')';
 }
 }
 }
 varnCount = 0;
 functionchessBoard(tr,tc,dr,dc,size)
 {
 vars,t;
 if(size == 1)return;
 s =size/2;
 t = ++nCount ;
 if(dr < tr + s && dc < tc +s)
 chessBoard(tr,tc,dr,dc,s);
 else
 {
 Matrix[tr+s-1][tc+s-1] = t;
 chessBoard(tr,tc,tr+s-1,tc+s-1,s);
 }
 if(dr < tr + s && dc >= tc + s )
 chessBoard(tr,tc+s,dr,dc,s);
 else
 {
 Matrix[tr+s-1][tc+s] = t;
 chessBoard(tr,tc+s,tr+s-1,tc+s,s);
 }
 if(dr >= tr + s && dc < tc + s)
 chessBoard(tr+s,tc,dr,dc,s);
 else
 {
 Matrix[tr+s][tc+s-1] = t;
 chessBoard(tr+s,tc,tr+s,tc+s-1,s);
 }
 if(dr >= tr + s && dc >= tc + s)
 chessBoard(tr+s,tc+s,dr,dc,s);
 else
 {
 Matrix[tr+s][tc+s] = t;
 chessBoard(tr+s,tc+s,tr+s,tc+s,s);
 }
 }
 }
</script>

棋盘覆盖的C语言代码我是参考课本的，为了能够把它用进JavaScript里面，突破口就是二维数组Matrix[][]，只要能够获得它计算之后整个数组的数据，那么就有思路了。要记住填写进表单里面的数据是在点击按钮之后才获取的，所以获取元素节点的代码要放在onclick里面。

相信看了本文案例你已经掌握了方法，更多精彩请关注Gxl网其它相关文章！

推荐阅读：

js寄生组合式继承使用详解

react-router4.0实现重定向与404功能

热心网友时间：2022-04-23 05:06

下面讨论棋盘覆盖问题中数据结构的设计。
（1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；
（2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；
（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标;
（4） L型骨牌：一个2^k×2^k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4^k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。
设全局变量t已初始化为0，分治法求解棋盘覆盖问题的算法用C++语言描述如下：
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
int s, t1; //t1表示本次覆盖所用L型骨牌的编号
if (size == 1) return; //棋盘只有一个方格且是特殊方格
t1 = ++t; // L型骨牌编号
s = size/2; // 划分棋盘
if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盘中
ChessBoard(tr, tc, dr, dc, s); //递归处理子棋盘
else{ //用 t1号L型骨牌覆盖右下角，再递归处理子棋盘
board[tr + s - 1][tc + s - 1] = t1;
ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
}
if (dr < tr + s && dc >= tc + s) //特殊方格在右上角子棋盘中
ChessBoard(tr, tc+s, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖左下角，再递归处理子棋盘
board[tr + s - 1][tc + s] = t1;
ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
}
if (dr >= tr + s && dc < tc + s) //特殊方格在左下角子棋盘中
ChessBoard(tr+s, tc, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖右上角，再递归处理子棋盘
board[tr + s][tc + s - 1] = t1;
ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
}
if (dr >= tr + s && dc >= tc + s) //特殊方格在右下角子棋盘中
ChessBoard(tr+s, tc+s, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖左上角，再递归处理子棋盘
board[tr + s][tc + s] = t1;
ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}