回 帖 发 新 帖 刷新版面

主题:[讨论]各位大虾,一个超难迷宫题!帮我改进一下

有1个N*N的迷宫矩阵,0代表无障碍,1代表有障碍(不能通过),有一个计分器,初始值为n*n,每经过一个“0”,就会自动扣除1分,问:最高能得多少分?
[样例]:
输入:
4                             7
0 0 1 1                       0 1 1 1 1 1 1
1 0 0 0                       0 0 0 1 1 0 0
0 0 0 1                       0 0 1 1 1 1 1
1 0 0 0                       0 1 0 1 1 1 1
输出:                        1 1 0 0 1 1 0
9                             0 0 0 0 0 0 0
(这个是对的)                输出:
                              36
                              (这个有点小问题,为什么每次都是34?)
CLS
OPEN "0541.in" FOR INPUT AS #1
INPUT #1, n
REDIM A(n + 2, n + 2)
FOR I = 1 TO n + 2
   A(1, I) = 1
NEXT I
FOR I = 1 TO n + 2
   A(n + 2, I) = 1
NEXT I
FOR I = 2 TO n + 1
   A(I, 1) = 1: A(I, n + 2) = 1
   FOR J = 2 TO n + 1
      INPUT #1, A(I, J)
   NEXT J
NEXT I
REDIM V(4, 2)
FOR I = 1 TO 4
   FOR J = 1 TO 2
      READ V(I, J)
   NEXT J
NEXT I
DIM x(1000), y(1000), S(1000)
DATA 0,1,1,0,0,-1,-1,0
p = 0: X1 = n + 1: Y1 = n + 1: x = 2: y = 1: I = 0
x(p) = x: y(p) = y
MAX = 0
DO
   I = I + 1
   IF I <= 4 THEN
      x = x(p) + V(I, 1): y = y(p) + V(I, 2)
      IF A(x, y) = 0 THEN
         p = p + 1
         PRINT x - 1; y - 1; n * n - p
         S(p) = I: x(p) = x: y(p) = y
         A(x, y) = 2: I = 0
         IF x = X1 AND y = Y1 THEN
            k = n * n - p
            IF k > MAX THEN MAX = k
         END IF
      END IF
   ELSE
      I = S(p): p = p - 1
   END IF
LOOP UNTIL p = 0
PRINT MAX
END
注:此程序用文件操作形式,0541.in内为输入内容

回复列表 (共19个回复)

沙发

tqw,我是把方向定义成了两个,只有向左和向下,就成功了

板凳

只有向左和向下就不存在绕弯路的情况了

3 楼

只有向左和向下,那样例怎么做呢?

4 楼

[样例修正]:
输入:
4                             7
0 0 1 1                       0 1 1 1 1 1 1
1 0 0 0                       0 0 0 1 1 0 0
0 0 0 1                       0 0 1 1 1 1 1
1 0 0 0                       0 1 0 1 1 1 1
输出:                        0 0 0 0 1 1 1
9                             1 1 0 0 1 1 0
(这个是对的)                0 0 0 0 0 0 0
                              输出:
                              36
                              (这个有点小问题,为什么每次都是34?)

5 楼

JRX,你04-4题13数据多少秒?

6 楼

1. 最高能得 n*n-(2*n-1) 分
   (只要没有回头的话,都是这个分数)

2. 得数34,是因为中间存在一个回头,所以多走了两步.

7 楼

[quote]JRX,你04-4题13数据多少秒?[/quote]
差不多一分钟以内,总之很慢了

8 楼

JRX:
   你的QB做1000000次循环要多少秒?
(把运行结果告诉我)
cls
t=timer
for i=1 to 1000000
next
? timer-t
end

9 楼

MOZ:
   谢谢,那程序该怎么改呢?
   我觉得要多定义两个数组,分别存放分支及0改成2的位置,但不知怎么改好!

10 楼

[quote]JRX:
&nbsp;&nbsp;&nbsp;你的QB做1000000次循环要多少秒?
(把运行结果告诉我)
cls
t=timer
for&nbsp;i=1&nbsp;to&nbsp;1000000
next
?&nbsp;timer-t
end[/quote]
运行结果:
.3320313
(用了1-2秒)

我来回复

您尚未登录,请登录后再回复。点此登录或注册