北大慕課プログラム設計とアルゴリズム(二)時計抜き問題
2267 ワード
説明
9つのクロックがあり、3*3のマトリクスに並んでいます.
最小の移動で、9クロックのポインタを12時の位置にダイヤルする必要があります.合計9種類の異なる移動が許可されています.以下の表に示すように、各移動は、複数のクロックのポインタを時計回りに90度動かします.
各クロックポインタの開始位置を表す9つの整数を入力し、隣接する2つの整数の間を単一のスペースで区切ります.ここで、0=12点、1=3点、2=6点、3=9点である.出力は、9クロックのポインタが12点を指すように最短の移動シーケンスを出力する.移動したシーケンス番号に従って、結果を小から大に出力します.隣接する2つの整数の間には、1つのスペースで区切られています.サンプル入力
1166
簡単な列挙問題は,すべての操作方式を列挙し,回数の最小の1回の操作を記録する.
acコード:
#include#include#include#include#include#includeusing namespace std;int oriclocks[9];int clocks[9];int movetime[9];int result[9];const char * moves[9]={ "ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};int minx=1<<30;void Enum(int n){ if(n==9){ memcpy(clocks,oriclocks,sizeof(clocks)); int t=0; for(int i=0;i<9;i++){ t+=movetime[i]; if(movetime[i]){ for(int j=0;moves[i][j];j++){ clocks[moves[i][j]-'A']=(clocks[moves[i][j]-'A']+movetime[i])%4; } } } int f=1; for(int i=0;i if(clocks[i]){ f=0; break; } } if(f){ if(t minx=t; memcpy(result,movetime,sizeof(result)); } } return ; } for(int i=0;i<4;i++){//ö¾ÙËùÓпÉÄÜ movetime[n]=i; Enum(n+1); }}int main(){ for(int i=0;i<9;i++){ cin>>oriclocks[i]; } Enum(0); for(int i=0;i<9;i++){ if(result[i]){ for(int j=0;j cout< } } } return 0;}
9つのクロックがあり、3*3のマトリクスに並んでいます.
|-------| |-------| |-------|
| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C
|-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F
|-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------|
G H I
( 1)最小の移動で、9クロックのポインタを12時の位置にダイヤルする必要があります.合計9種類の異なる移動が許可されています.以下の表に示すように、各移動は、複数のクロックのポインタを時計回りに90度動かします.
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI
各クロックポインタの開始位置を表す9つの整数を入力し、隣接する2つの整数の間を単一のスペースで区切ります.ここで、0=12点、1=3点、2=6点、3=9点である.出力は、9クロックのポインタが12点を指すように最短の移動シーケンスを出力する.移動したシーケンス番号に従って、結果を小から大に出力します.隣接する2つの整数の間には、1つのスペースで区切られています.サンプル入力
3 3 0
2 2 2
2 1 2 4 5 8 9 1166
簡単な列挙問題は,すべての操作方式を列挙し,回数の最小の1回の操作を記録する.
acコード:
#include#include#include#include#include#includeusing namespace std;int oriclocks[9];int clocks[9];int movetime[9];int result[9];const char * moves[9]={ "ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};int minx=1<<30;void Enum(int n){ if(n==9){ memcpy(clocks,oriclocks,sizeof(clocks)); int t=0; for(int i=0;i<9;i++){ t+=movetime[i]; if(movetime[i]){ for(int j=0;moves[i][j];j++){ clocks[moves[i][j]-'A']=(clocks[moves[i][j]-'A']+movetime[i])%4; } } } int f=1; for(int i=0;i if(clocks[i]){ f=0; break; } } if(f){ if(t minx=t; memcpy(result,movetime,sizeof(result)); } } return ; } for(int i=0;i<4;i++){//ö¾ÙËùÓпÉÄÜ movetime[n]=i; Enum(n+1); }}int main(){ for(int i=0;i<9;i++){ cin>>oriclocks[i]; } Enum(0); for(int i=0;i<9;i++){ if(result[i]){ for(int j=0;j cout< } } } return 0;}