认为自己牛的进来吧 ( 积分: 100 )

世界名画陈列馆由m×n个陈列室组成。为防止名画被窃，需在陈列室中设置警卫机器人哨
位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在陈列室相邻的前、
后、左、右4个陈列室。请设计一个安排警卫机器人哨位的方案，使得名画陈列馆中每一个
陈列室都在警卫机器人监视之下，且所用的警卫机器人最少。

哪位牛人对此题有什么想法，畅所欲言吧^_^

楼主肯定是个学生，数据结构没学好，到这儿用激将法找人给你做题目了：）

dingbaosheng 好眼光.
送几句话给楼主, 做人要低调.

无语^…………不知道说什么好，

..。。。。。。。。。被你说对了。。可是你的回答没用呀

这个问题就是等价于拼十字型地砖的问题，不够放一个十字砖的地方就必须打碎一个砖。
怎样用最少的砖。和地砖师付的还有所不同，他可以打碎一个地砖为几块分别用在不同的地方，而这个不行。

好象有一个数据结构中的国际象棋中的皇后问题和这个差不多,懒的查了

更新机器人版本!
可以监视n x m的就可以用最少
当然,你请警卫就可以不用机器人
zheng jie

我认为dingbaosheng, 回答最一针见血

dingbaosheng 真是高人阿

说实话，会，但不告诉你...
论坛里，楼主最牛，你问自己去吧...

对不起了,我新手.关注进展~~~~

我误闯牛栏了

每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在陈列室相邻的前、
后、左、右4个陈列室。
-------------------------------------------------------------------
脑筋急转弯,一个.

哎,这题还真不需要牛人来解决,死套公式实现了一下,貌似能出结果.
想优化这种算法得在逻辑表达式化简上下工夫,那才是牛人干的呢.
program Project2;
{$APPTYPE CONSOLE}
type
TSet = set of Byte;
TResult = array of TSet;
var
M, N: Integer;
NodeNum: Integer;
NewSet: TSet;
i, j, k: Integer;
d, Index: Integer;
r, tr: TResult;
Add: Boolean;
Best, BestPos: Integer;
function Delta(const Index, d: Integer): Integer;
begin
case d of
1: Result:=Index;
2: if Index<M then
Result:=-1
else
Result:=Index-M;
3: if (Index mod M)>=(M-1) then
Result:=-1
else
Result:=Index+1;
4: if (Index div M)>=(N-1) then
Result:=-1
else
Result:=Index+M;
5: if (Index mod M)=0 then
Result:=-1
else
Result:=Index-1
else
Result:=-1
end
end;

function TrueLength(const ASet: TSet): Integer;
var
i: Integer;
begin
Result:=0;
for i:=0 to NodeNum-1do
if (i in ASet) then
Inc(Result)
end;

procedure Print(const ASet: TSet);
var
x, y, Index: Integer;
begin
for x:=0 to N-1do
begin
for y:=0 to M-1do
begin
Index:=x*M+y;
if (Index in ASet) then
Write('0': 2)
else
Write('*': 2)
end;
WriteLn
end
end;

begin
Write('M=');
ReadLn(M);
Write('N=');
ReadLn(N);
NodeNum:=M*N;
if (NodeNum>0) and (NodeNum<256) then
begin
for d:=1 to 5do
begin
Index:=Delta(0, d);
if Index>=0 then
begin
SetLength(r, Length(r)+1);
r[Length(r)-1]:=[Index]
end
end;

for i:=1 to NodeNum-1do
begin
SetLength(tr, Length(r));
for j:=0 to Length(r)-1do
tr[j]:=r[j];
SetLength(r, 0);
for d:=1 to 5do
begin
Index:=Delta(i, d);
if Index>=0 then
for j:=0 to Length(tr)-1do
begin
NewSet:=tr[j]+[Index];
Add:=True;
k:=0;
while Add and (k<Length(r))do
if NewSet*r[k]=r[k] then
Add:=False
else
if NewSet*r[k]=NewSet then
begin
r[k]:=r[Length(r)-1];
SetLength(r, Length(r)-1)
end
else
Inc(k);
if Add then
begin
SetLength(r, Length(r)+1);
r[Length(r)-1]:=NewSet
end
end
end
end;

Best:=MaxInt;
BestPos:=-1;
for i:=0 to Length(r)-1do
begin
j:=TrueLength(r);
if j<Best then
begin
Best:=j;
BestPos:=i
end
end;

if BestPos>=0 then
Print(r[BestPos])
end
else
WriteLn('Error');
ReadLn
end.

非常敬佩这位大牛，不知能否认识一下