格子状経路

 投稿者：山中和義  投稿日：2015年 5月20日(水)10時31分42秒
  問題
町が碁盤の目の様な道路になっており、座標平面上の格子点を動くように散歩するものとする。
その人の座標が(a,b)で
　a+b≡0 mod 4のとき、右へ1進む。
　a+b≡1 mod 4のとき、上へ1進む。
　a+b≡2 mod 4のとき、左へ1進む。
　a+b≡3 mod 4のとき、下へ1進む。
と進路をとって進むものとする。
このとき、ある格子点Pから散歩を始めた人が、
進路変更を9回繰り返したとき、格子点Q(0,10)に到着していたという。
さて出発点の格子点Pとして考えられるのはどこですか？

答え　(5,5)


SET WINDOW -1,12,-1,12
DRAW grid
FOR A=-1 TO 12 !(a,b)
   FOR B=-1 TO 12
      DRAW AR WITH ROTATE((A+B)*(2*PI/4))*SHIFT(A,B)
   NEXT B
NEXT A
END
EXTERNAL PICTURE AR !矢印を描く
PLOT LINES: 0,0; 0.5,0 !→
PLOT LINES: 0.5,0; 0.3,0.1
PLOT LINES: 0.5,0; 0.3,-0.1
END PICTURE
 

Re: 格子状経路

 投稿者：GAI  投稿日：2015年 5月20日(水)20時50分1秒
  > No.3698[元記事へ]

山中和義さんへのお返事です。

>
> 答え　(5,5)
>

(3,5)もOKです。
思考してた経緯が、プログラムで見れるのがとっても参考にできます。
これが自由にできるようになれば、あのめんどくさい作業が一瞬にできるのにと痛感します。
 		 

Re: 格子状経路

 投稿者：しばっち  投稿日：2015年 5月21日(木)23時50分4秒
  > No.3698[元記事へ]

山中和義さんへのお返事です。

FOR YS=1 TO 10
   FOR XS=1 TO 10
      LET X=XS
      LET Y=YS
      FOR I=0 TO 9
         SELECT CASE MOD(X+Y,4)
         CASE 0
            LET X=X+1
         CASE 1
            LET Y=Y+1
         CASE 2
            LET X=X-1
         CASE 3
            LET Y=Y-1
         END SELECT
      NEXT I
      IF X=0 AND Y=10 THEN PRINT XS;YS
      !' PRINT XS;YS;X;Y
   NEXT XS
NEXT YS
END
 		 

格子状経路

 投稿者：山中和義  投稿日：2015年 6月 9日(火)18時58分54秒
  > No.3698[元記事へ]

問題
下図のような格子状経路の移動を考える。
左下（交差点1）からその右（交差点2）に進み、各交差点を1回のみ通って、
交差点20に進む道順は何通りあるか。

・─・─・─・─・
│　│　│　│　│
・─・─・─・─・
↓　│　│　│　│
20←・─・─・─・
↓　↑　│　│　│
１→２→・─・─・

考察
四隅は一方通行となる。
・←●─・─○←・
↓　│　│　│　↑
○─・─・─・─●
↓　│　│　│　│
20←・─・─・─○
↓　↑　│　│　↑
１→２→・─●→・

m=4、n=11以降は処理困難となる。




LET M=4 !m行n列　※交差点の個数
LET N=5
DIM A(M,N)
MAT A=ZER
LET A(M,1)=1 !始点
LET A(M,2)=2
PUBLIC NUMERIC C !場合の数
LET C=0
CALL try(3,M,2, M,N,A)
PRINT C;"通り"
END
EXTERNAL SUB try(P,Y,X, M,N,A(,))
IF Y=M-1 AND X=1 THEN !終点
   IF P>M*N THEN
      LET C=C+1 !結果を表示する
      PRINT "No.";C
      MAT PRINT USING REPEAT$(" ##",N): A
   END IF
ELSE
   DIM B(M,N)
   MAT B=A
   IF Y>1 AND A(Y-1,X)=0 THEN !上へ
      LET B(Y-1,X)=P
      CALL try(P+1,Y-1,X, M,N,B)
      LET B(Y-1,X)=0
   END IF
   IF Y<M AND A(Y+1,X)=0 THEN !下へ
      LET B(Y+1,X)=P
      CALL try(P+1,Y+1,X, M,N,B)
      LET B(Y+1,X)=0
   END IF
   IF X>1 AND A(Y,X-1)=0 THEN !左へ
      LET B(Y,X-1)=P
      CALL try(P+1,Y,X-1, M,N,B)
      LET B(Y,X-1)=0
   END IF
   IF X<N AND A(Y,X+1)=0 THEN !右へ
      LET B(Y,X+1)=P
      CALL try(P+1,Y,X+1, M,N,B)
      LET B(Y,X+1)=0
   END IF
END IF
END SUB


実行結果

No. 1
18 17 16 15 14
19  4  5 12 13
20  3  6 11 10
  1  2  7  8  9
No. 2
18 17 16 15 14
19  4  5  6 13
20  3  8  7 12
  1  2  9 10 11
No. 3
18 17 14 13 12
19 16 15 10 11
20  3  4  9  8
  1  2  5  6  7
No. 4
16 15 14 13 12
17 18  5  6 11
20 19  4  7 10
  1  2  3  8  9
No. 5
18 17 16 15 14
19  6  7  8 13
20  5  4  9 12
  1  2  3 10 11
No. 6
16 15 14 11 10
17 18 13 12  9
20 19  4  5  8
  1  2  3  6  7
No. 7
16 15 14  9  8
17 18 13 10  7
20 19 12 11  6
  1  2  3  4  5
No. 8
18 17 16  9  8
19 14 15 10  7
20 13 12 11  6
  1  2  3  4  5
No. 9
18 17 10  9  8
19 16 11 12  7
20 15 14 13  6
  1  2  3  4  5
No. 10
12 11 10  9  8
13 14 15 16  7
20 19 18 17  6
  1  2  3  4  5
No. 11
18 17 12 11 10
19 16 13  8  9
20 15 14  7  6
  1  2  3  4  5
No. 12
14 13 12 11 10
15 16 17  8  9
20 19 18  7  6
  1  2  3  4  5
No. 13
16 15 14 13 12
17 18  9 10 11
20 19  8  7  6
  1  2  3  4  5
No. 14
18 17 16 15 14
19 10 11 12 13
20  9  8  7  6
  1  2  3  4  5
14 通り


 		 

戻る