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 보다 각은 면적을 가진 체스판이다. 기사는 이동할 때 두 칸 이동하고 직각으로 한 칸 이동한다.
+=== 입력 ===
+입력은 첫 번째 라인에 양의 정수 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 ===
+1
+3
+3
+=== Sample Output ===
+ Scenario #1:
+ A1
-  char* GetPath(int k)
+  Scenario #2:
-  {
+  impossible
- 	switch(k){
- 		case 101:	return "A1";
- 		case 304:	return "A1C2A3B1D2B3C1A2C3D1B2D3";
- 		case 307:	return "A1B3D2F1G3E2G1F3E1G2E3C2A3B1C3A2C1D3B2D1F2";
- 		case 308:	return "A1B3C1A2C3D1B2D3E1G2E3C2A3B1D2F1H2F3G1E2G3H1F2H3";
- 		case 403:	return "A1B3C1A2B4C2A3B1C3A4B2C4";
- 		case 405:	return "A1B3C1A2B4D3E1C2D4E2C3A4B2D1E3C4A3B1D2E4";
- 		case 406:	return "A1B3C1A2B4C2D4E2F4D3E1F3D2B1A3C4B2A4C3E4F2D1E3F1";
- 		case 504:	return "A1B3A5C4D2B1A3B5D4C2B4A2C1D3C5A4B2D1C3D5";
- 		case 505:	return "A1B3A5C4A3B1D2E4C5A4B2D1C3B5D4E2C1A2B4D5E3C2E1D3E5";
- 		case 604:	return "A1B3A5C6D4B5D6C4D2B1A3C2B4A2C1D3B2D1C3D5B6A4C5A6";
- 		case 703:	return "A1B3C1A2C3B1A3C2B4A6C7B5A7C6A5B7C5A4B2C4B6";
- 		case 803:	return "A1B3C1A2B4C2A3B1C3A4B2C4A5B7C5A6B8C6A7B5C7A8B6C8";
- 		default:	return "impossible";
- 	}
- }
- int main()
- {
- 	int i, n, p, q;
- 	scanf("%d", &amp;n);
+ Scenario #3:
- 	for(i=1;i&lt;=n;i++){
+  A1B3C1A2B4C2A3B1C3A4B2C4
- 		scanf("%d %d", &amp;p, &amp;q);
+=== 풀이 ===
- 		printf("Scenario #%d:\n%s\n\n", i, GetPath(p*100+q));
+{| class="wikitable"
- 	}
+|-
- 	return 0;
+| 작성자
-  }
+| 사용언어
+| 개발시간
-/// C
+| 코드
+|-
- A[30][30],P,Q,F=1,C[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}},N;char B[99];
+| [[정진경]]
- main(i,j,n){
+| .
- 	if(F)
+| -
- 		for(i=scanf("%d",&amp;n);N=i&lt;=n;main(1,1),printf("Scenario #%d:\n%s\n\n",i++,F?B:"impossible"),memset(A,0,3600))
+| [[AKnight'sJourney/정진경|AKnight's Journey/정진경]]
- 			B[scanf("%d %d",&amp;P,&amp;Q)*P*Q]=F=0;
+|-
- 	else
+| [[강소현]]
- 		if(F|1&gt;i|i&gt;P|1&gt;j|j&gt;Q|A[i][j]);
+| 사용언어
- 		else{
+| 개발시간
- 			for(B[N*2-2]=j+64,B[N*2-1]=i+48,n=F=N==P*Q,A[i][j]=N++;n&lt;8&amp;&amp;!F;main(i+C[n++][0],j+C[n][1]));
+| [[AKnight'sJourney/강소현|AKnight's Journey/강소현]]
- 			A[i][j]-=--N;
+|}
- 		}
- }
-=== ... ===
-* 음... 어디가 틀렸을까요 -[[정진경]]
+----
-* 난데없이 억셉트가 되버렸다. -[[정진경]]
+[http://poj.org/problem?id=2488 Problem A Knight's journey], [[문제분류]], [[ACM_ICPC/2011년스터디]]