AKnight'sJourney: Difference between revisions

Latest revision as of 01:53, 16 November 2013

A Knight's Journey

Time Limit	1000MS	Memory Limit	65536K
Total Submissions	15350	Accepted	5124

배경

기사는 또 다시 같은 검은색과 흰색 사각형을 보는 것이 지루해 전 세계를 여행하기로 결심했다. 기사의 세계는 8*8 보다 각은 면적을 가진 체스판이다. 기사는 이동할 때 두 칸 이동하고 직각으로 한 칸 이동한다.

입력

입력은 첫 번째 라인에 양의 정수 N과 함께 시작됩니다. 다음 라인은 N 개의 테스트 케이스가 포함되어 있습니다. 각 테스트 케이스는 두 양의 정수 P와 Q로 이루어져 있는데, 1<= P * Q <= 26 로 제한이 되어있습니다. P*Q 체스판에서 P는 1, 2, ..., p , Q는 A, B, C, ..., Q를 나타냅니다.

출력

시나리오 시작 번호는 1입니다. 모든 시나리오에 대한 출력은 "Scenario # I:"으로 시작합니다. 다음 기사 이동과 체스판의 모든 사각형을 방문하는 순서는 사전 편찬(집필) 상의 순서를 따라야 합니다. 방문 가능한 경로는 여러 가지가 있을 수 있지만, ABC, 123 의 순서를 따지면 결과는 하나로 정해져 있습니다. 최종 경로는 한 줄에 제공해야합니다. 전부 방문할 수 있는 경로가 존재하지 않으면, 당신이 한 줄에 출력 불가능합니다.

Sample Input

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

풀이

작성자	사용언어	개발시간	코드
정진경	.	-	AKnight's Journey/정진경
강소현	사용언어	개발시간	AKnight's Journey/강소현

Problem A Knight's journey, 문제분류, ACM_ICPC/2011년스터디

@@ Line 1: / Line 1: @@
-Describe AKnight'sJourney here
+== A Knight's Journey ==
+{| class="wikitable"
+|-
+| Time Limit
+| 1000MS
+| Memory Limit
+| 65536K
+|-
+| Total Submissions
+| 15350
+| Accepted
+| 5124
+|}
-=== Source Code ===
+=== 배경 ===
- #include &lt;stdio.h&gt;
+기사는 또 다시 같은 검은색과 흰색 사각형을 보는 것이 지루해 '''전 세계'''를 여행하기로 결심했다. 기사의 세계는 8*8 보다 각은 면적을 가진 체스판이다. 기사는 이동할 때 두 칸 이동하고 직각으로 한 칸 이동한다.
- #include &lt;memory.h&gt;
+=== 입력 ===
- int A[30][30];
+입력은 첫 번째 라인에 양의 정수 N과 함께 시작됩니다. 다음 라인은 N 개의 테스트 케이스가 포함되어 있습니다. 각 테스트 케이스는 두 양의 정수 P와 Q로 이루어져 있는데, 1<= P * Q <= 26 로 제한이 되어있습니다. P*Q 체스판에서 P는 1, 2, ..., p , Q는 A, B, C, ..., Q를 나타냅니다.
- int B[700][2];
- int P, Q;
+=== 출력 ===
- short Flag;
+시나리오 시작 번호는 1입니다. 모든 시나리오에 대한 출력은 "Scenario # I:"으로 시작합니다. 다음 기사 이동과 체스판의 모든 사각형을 방문하는 순서는 '''사전 편찬(집필) 상의 순서'''를 따라야 합니다. 방문 가능한 경로는 여러 가지가 있을 수 있지만, ABC, 123 의 순서를 따지면 결과는 하나로 정해져 있습니다. 최종 경로는 한 줄에 제공해야합니다. 전부 방문할 수 있는 경로가 존재하지 않으면, 당신이 한 줄에 출력 불가능합니다.
- void R(int n, int p, int q)
+=== Sample Input ===
- {
- 	if(Flag){
+1
- 		return;
+3
- 	}else if(1&gt;p || p&gt;P || 1&gt;q || q&gt;Q || A[p][q]){
+3
- 		return;
- 	}else if(n==P*Q){
+=== Sample Output ===
- 		B[n][0]=p;
+ Scenario #1:
- 		B[n][1]=q;
+ A1
- 		Flag=1;
- 		return;
- 	}else{
- 		B[n][0]=p;
- 		B[n][1]=q;
- 		A[p][q]=1;
- 		R(n+1, p-2, q-1);
+ Scenario #2:
- 		R(n+1, p-2, q+1);
+ impossible
- 		R(n+1, p-1, q-2);
- 		R(n+1, p-1, q+2);
- 		R(n+1, p+1, q-2);
- 		R(n+1, p+1, q+2);
- 		R(n+1, p+2, q-1);
- 		R(n+1, p+2, q+1);
- 		if(Flag){
+ Scenario #3:
- 			return;
+ A1B3C1A2B4C2A3B1C3A4B2C4
- 		}
+=== 풀이 ===
- 		A[p][q]=0;
+{| class="wikitable"
- 		B[n][0]=0;
+|-
- 		B[n][1]=0;
+| 작성자
- 	}
+| 사용언어
- }
+| 개발시간
+| 코드
- void solve()
+|-
- {
+| [[정진경]]
- 	int p, q;
+| .
+| -
- 	scanf("%d %d", &amp;P, &amp;Q);
+| [[AKnight'sJourney/정진경|AKnight's Journey/정진경]]
+|-
- 	for(p=1; p&lt;=P; p++){
+| [[강소현]]
- 		for(q=1; q&lt;=Q; q++){
+| 사용언어
- 			if(!Flag){
+| 개발시간
- 				R(1, p, q);
+| [[AKnight'sJourney/강소현|AKnight's Journey/강소현]]
- 			}else{
+|}
- 				return;
- 			}
- 		}
- 	}
- }
- int main()
- {
- 	int n;
- 	int i, j;
- 	scanf("%d", &amp;n);
- 	for(i=1; i&lt;=n; i++){
- 		Flag=0;
- 		memset(A, 0, sizeof(A));
- 		printf("Scenario #%d\n", i);
- 		solve();
- 		if(Flag){
- 			for(j=1; j&lt;=P*Q; j++){
- 				printf("%c%c", B[j][1]+'A'-1, B[j][0]+'0');
- 			}
- 		}else{
- 			printf("impossible");
- 		}
- 		printf("\n\n");
- 	}
- 	return 0;
- }
-/// WA C
-=== ... ===
-* 음... 어디가 틀렸을까요 -[[정진경]]
+----
+[http://poj.org/problem?id=2488 Problem A Knight's journey], [[문제분류]], [[ACM_ICPC/2011년스터디]]