主题:[讨论]各位大虾,一个超难迷宫题!帮我改进一下
小小tqw [专家分:40] 发布于 2006-08-07 09:45:00
有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 楼
小小tqw [专家分:40] 发布于 2006-08-07 11:45:00
re JRX:
挺快的!
是QB4.5吗?
好像QB7.0才能到这个速度!
12 楼
JRX [专家分:180] 发布于 2006-08-07 11:47:00
[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 楼
小小tqw [专家分:40] 发布于 2006-08-07 11:49:00
JRX:
我又发新贴了,编得好我再给你加30分!
14 楼
小小tqw [专家分:40] 发布于 2006-08-07 12:11:00
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 楼
609802597 [专家分:20] 发布于 2006-08-10 20:01:00
可以这样做:
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 楼
小小tqw [专家分:40] 发布于 2006-08-13 10:30:00
引用:
[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 楼
maxumi [专家分:2200] 发布于 2006-09-06 17:12:00
用动态规划很快的
18 楼
phile [专家分:2310] 发布于 2009-07-22 11:43:00
我用递归
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 楼
593170024 [专家分:500] 发布于 2009-10-26 12:31:00
只有向左和向下就行了
我来回复