回 帖 发 新 帖 刷新版面

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

有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个回复)

11 楼

re JRX:
挺快的!
是QB4.5吗?
好像QB7.0才能到这个速度!

12 楼

[quote]只有向左和向下,那样例怎么做呢?[/quote]
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 [color=FF0000]2[/color]    '把4改成2,因为只有两个方向
   FOR J = 1 TO 2
      READ V(I, J)
   NEXT J
NEXT I
DIM x(1000), y(1000), S(1000)
DATA [color=FF0000]0,1,1,0[/color]      '保留向左和向下两个方向的
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 <= [color=FF0000]2[/color] THEN     '因为只有两个方向,所以改成I<= 2
      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

13 楼

JRX:
我又发新贴了,编得好我再给你加30分!

14 楼

5
0 0 0 0 0
1 1 1 1 0
0 0 0 0 0              
0 1 1 1 1 
0 0 0 0 0
这个数据你的输出是0,但答案是8。

15 楼

可以这样做:

CLS
DIM s(1000), x(1000), y(1000)
FOR K = 1 TO 4
  FOR J = 1 TO 4
    READ A(K, J)
  NEXT J
NEXT K
q = 16
DATA 0,0,1,1
DATA 1,0,0,0
DATA 0,0,0,1
DATA 1,0,0,0
FOR i = 1 TO 4
  FOR J = 1 TO 2
   READ V(i, J)
  NEXT J
NEXT i
DATA 0,1,1,0,-1,0,0,-1
i = 0
p = 1
x = 1
y = 1
x(p) = x
y(p) = y
xe = 4
ye = 4
DO
  i = i + 1
  IF i <= 4 THEN
    x = x(p) + V(i, 1)
    y = y(p) + V(i, 2)
    IF x <= 4 AND x >= 1 AND y <= 4 AND y >= 1 THEN
      IF A(x, y) = 0 THEN
        p = p + 1
        s(p) = i
        x(p) = x
        y(p) = y
        i = 0
        A(x, y) = 2
      IF x = xe AND y = ye THEN
        GOSUB 10
      PRINT q
      END IF
      END IF
    END IF
  ELSE
    i = s(p)
    p = p - 1
END IF
LOOP UNTIL x = xe AND y = ye OR p = 0
END
10  FOR J = 1 TO p
      PRINT "("; x(J); ","; y(J); ")"
    NEXT J
   q = q - p
RETURN

16 楼

引用:
[color=FF0000]输入:
4                             7
0 0 1 1                       [b]0 1 1 1 1 1 1[/b]
1 0 0 0                       [b]0 0 0 1 1 0 0[/b]
0 0 0 1                       [b]0 0 1 1 1 1 1[/b]
1 0 0 0                       [b]0 1 0 1 1 1 1[/b]
输出:                        [b]0 0 0 0 1 1 1[/b]
9                             [b]1 1 0 0 1 1 0[/b]
(这个是对的)                [b]0 0 0 0 0 0 0[/b]
                              输出:
                              36
                              (这个有点小问题,为什么每次都是34?)[/color]
第二个不对[em1]

17 楼

用动态规划很快的

18 楼

我用递归
CLS
INPUT N
DIM A(N, N)
FOR I = 1 TO N
  FOR J = 1 TO N
    INPUT A(I, J)
NEXT J, I
CLS
FOR I = 1 TO N
  FOR J = 1 TO N
    PRINT USING "##"; A(I, J);
  NEXT J
  PRINT
NEXT I
I = 1
J = 1
S = N * N - 1
GOSUB 100
END
100
IF A(I, J) = 0 THEN
  A(I, J) = 2
  IF I = N AND J = N THEN PRINT S: END
  S = S - 1
  I = I + 1
  IF I <= N THEN GOSUB 100
  I = I - 1
  S = S + 1
  S = S - 1
  J = J + 1
  IF J <= N THEN GOSUB 100
  J = J - 1
  S = S + 1
  S = S - 1
  I = I - 1
  IF I > 0 THEN GOSUB 100
  S = S + 1
  I = I + 1
  S = S - 1
  J = J - 1
  IF J > 0 THEN GOSUB 100
  J = J + 1
  S = S + 1
  A(I, J) = 0
END IF
RETURN
  

19 楼

只有向左和向下就行了

我来回复

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