主题:[讨论]各位大虾,一个超难迷宫题!帮我改进一下
小小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个回复)
沙发
JRX [专家分:180] 发布于 2006-08-07 09:48:00
tqw,我是把方向定义成了两个,只有向左和向下,就成功了
板凳
JRX [专家分:180] 发布于 2006-08-07 09:48:00
只有向左和向下就不存在绕弯路的情况了
3 楼
小小tqw [专家分:40] 发布于 2006-08-07 10:40:00
只有向左和向下,那样例怎么做呢?
4 楼
小小tqw [专家分:40] 发布于 2006-08-07 10:43:00
[样例修正]:
输入:
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 楼
小小tqw [专家分:40] 发布于 2006-08-07 10:45:00
JRX,你04-4题13数据多少秒?
6 楼
moz [专家分:37620] 发布于 2006-08-07 11:04:00
1. 最高能得 n*n-(2*n-1) 分
(只要没有回头的话,都是这个分数)
2. 得数34,是因为中间存在一个回头,所以多走了两步.
7 楼
JRX [专家分:180] 发布于 2006-08-07 11:12:00
[quote]JRX,你04-4题13数据多少秒?[/quote]
差不多一分钟以内,总之很慢了
8 楼
小小tqw [专家分:40] 发布于 2006-08-07 11:30:00
JRX:
你的QB做1000000次循环要多少秒?
(把运行结果告诉我)
cls
t=timer
for i=1 to 1000000
next
? timer-t
end
9 楼
小小tqw [专家分:40] 发布于 2006-08-07 11:34:00
MOZ:
谢谢,那程序该怎么改呢?
我觉得要多定义两个数组,分别存放分支及0改成2的位置,但不知怎么改好!
10 楼
JRX [专家分:180] 发布于 2006-08-07 11:42:00
[quote]JRX:
你的QB做1000000次循环要多少秒?
(把运行结果告诉我)
cls
t=timer
for i=1 to 1000000
next
? timer-t
end[/quote]
运行结果:
.3320313
(用了1-2秒)
我来回复