我正在创建一个允许用户绘制平面图的应用程序。它为他们提供了 12 x 8 的网格，并允许他们点击最多 50 个正方形。当他们达到 50 时，他们会停止，但他们可以单击已选择的正方形将其变为空白，然后选择另一个。
我需要做的是检查计划。他们中间不能有任何缝隙。所有方格只能在四个主要方向(无对 Angular 线)从所有其他方格进入。
是否有某种函数可以想象一个人站在第一个方格中并确保他可以访问所有其他方格。
如果需要，我愿意使用 php 或 JavaScript。周围是否有任何东西可以做到这一点，或者有人能够帮助我。
下面是创建平面图的代码。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>Plan</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"/>
<script type="text/javascript">
<!--
var count=0;
function plan(id)
{
var obj = document.getElementById(id);
if(obj.style.backgroundColor == "rgb(0, 0, 0)")
{
if(count <= 49)
{
count++;
}
else
{
alert('You can have a maximum of 50');
count++;
}
}
else if(obj.style.backgroundColor == "rgb(255, 0, 0)")
{
count--;
}
if(count <= 50)
{
obj.style.backgroundColor = (obj.style.backgroundColor == "rgb(0, 0, 0)") ? "#ff0000" : "#000000";
obj.style.color = (obj.style.backgroundColor == "rgb(0, 0, 0)") ? "#000000" : "#ffffff";
}
if (count>50)
{
count--;
}
}
function number()
{
var room_number=0;
col=0;
row="a";
for (var i=1; i<97; i++)
{
col++;
if (i<97)
{
row="h";
}
if (i<85)
{
row="g";
}
if (i<73)
{
row="f";
}
if (i<61)
{
row="e";
}
if (i<49)
{
row="d";
}
if (i<37)
{
row="c";
}
if (i<25)
{
row="b";
}
if (i<13)
{
row="a";
}
if (col>12)
{
col=1;
}
var room = document.getElementById(row+col);
if (room.style.backgroundColor == "rgb(255, 0, 0)")
{
room_number++;
room.textContent=room_number;
}
else
{
room.textContent="";
}
}
}
//-->
</script>
</head>
<body style="background-color: #000000; width: 386px; margin: 10px auto 0;">
<?php
$l=0;
$j=0;
for ($i=0; $i<96; $i++)
{
$l++;
$j++;
if ($j<97)
{
$letter=h;
}
if ($j<85)
{
$letter=g;
}
if ($j<73)
{
$letter=f;
}
if ($j<61)
{
$letter=e;
}
if ($j<49)
{
$letter=d;
}
if ($j<37)
{
$letter=c;
}
if ($j<25)
{
$letter=b;
}
if ($j<13)
{
$letter=a;
}
if ($l>12)
{
$l=1;
}
$border="2px 0 0 2px";
if ($l==12)
{
$border="2px 2px 0 2px";
}
if ($j>84)
{
$border="2px 0 2px 2px";
}
if ($j==96)
{
$border="2px 2px 2px 2px";
}
?>
<div style="width: 30px; height: 30px; line-height: 30px; border-style: solid; border-color: #ffffff; border-width: <?=$border;?>; float: left; background-color: #000000; color: #ffffff; text-align: center; vertical-align: middle; font-weight: 700;" id="<?=$letter, $l;?>" onclick="plan('<?=$letter, $l;?>');"> </div>
<?php
}
?>
<input type="button" value="Done" onclick="number();"/>
</body>
</html>
最佳答案
您所描述的基本上是 Connected Graph problem ，但以一种更简单的方式 - 您所关心的是，对于每个选择的方 block ，如果它不是迄今为止选择的唯一一个，那么它有一个不为空的相邻方 block 。 您可以确保在每个方 block 标记后都保持这个不变式，但是在将方 block 变成空白后，您还必须通过确保每个现在空白的方 block 邻居都有一个选定的邻居来测试它。
就代码而言，您当前的解决方案似乎有点缺乏。 您依靠方形背景来确定它是否被选择，这不是一个好主意 - 想象一下稍后您想要从 CSS 文件控制此颜色或允许多种颜色。它会变得困惑。
我建议您创建一个数据结构来保存网格，并为每个方 block 保存代表该方 block 状态的数据。例如，一个 12x8 矩阵，如果方格为空，则为 0；如果选择方格，则为 1。这样，搜索方形邻居比遍历 DOM 容易得多。为每个绘制的正方形提供一个在 (1..12, 1..8) 范围内的坐标，并在通过 PHP 创建文档时将该坐标分配给每个正方形的 onclick 操作。例如，PHP 绘图可以通过以下方式完成:
<?php
for ($i = 1; $i <= 12; ++$i) {
for ($j = 1; $j <= 8; ++$j) {
?>
<div style="width: 30px; height: 30px; line-height: 30px; border-style: solid; border-color: #ffffff; border-width: <?=$border;?>; float: left; background-color: #000000; color: #ffffff; text-align: center; vertical-align: middle; font-weight: 700;" id="<?=$letter, $l;?>" onclick="plan(<?=$i;?>, <?=$j;?>, '<?=$letter, $l;?>');"> </div>
<?php
}
}
?>
然后处理提供给 plan() 的 ($i, $j) 坐标，以更新表示网格的 JavaScript 矩阵中的右侧方 block 。
您可以按如下方式初始化 JavaScript 矩阵 (wrapped up in a nice jsFiddle) :
var maxY = 12;
var maxX = 8;
var grid = new Array(maxY);
for (var i = 0; i < maxY; ++i) {
grid[i] = new Array(maxX);
for (var j = 0; j < maxX; ++j) {
grid[i][j] = 0;
}
}
function checkConnectedSquare(grid, y, x) {
// one of the neighbors must be chosen
return (x > 0 && grid[y][x-1] == 1)
|| (x < maxX-1 && grid[y][x+1] == 1)
|| (y > 0 && grid[y-1][x] == 1)
|| (y < maxY-1 && grid[y+1][x] == 1);
}
function checkConnected(grid) {
var countChosenSquares = 0;
var isConnected = true;
for (var i = 0; i < maxY; ++i) {
for (var j = 0; j < maxX; ++j) {
if (grid[i][j] == 1) {
if (!checkConnectedSquare(grid, i, j)) {
isConnected = false;
}
countChosenSquares++;
}
}
}
// if no squares were chosen or only one, the grid is 'connected'
// or every square that is chosen is connected.
return (countChosenSquares <= 1 || isConnected);
}
// test the code
function printGrid(grid) {
var html = '';
for (var i = 0; i < maxY; ++i) {
for (var j = 0; j < maxX; ++j) {
html += grid[i][j] + ' ';
}
html += '<br />';
}
document.body.innerHTML = html;
}
grid[3][6] = 1;
grid[3][7] = 1;
// should be true
console.log(checkConnectedSquare(grid, 3, 6));
// should be true
console.log(checkConnectedSquare(grid, 3, 7));
// should be false
console.log(checkConnectedSquare(grid, 2, 5));
// should be true
console.log(checkConnected(grid));
grid[2][5] = 1;
// should be false
console.log(checkConnected(grid));
grid[2][5] = 0;
grid[3][6] = 0;
// should be true
console.log(checkConnected(grid));
printGrid(grid);
作为奖励，您还可以保存对表示该正方形的 DOM 元素的引用，以便轻松更新网格。
关于javascript - 检查计划功能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22329882/