FilesExpand file tree

 master

/

clocks2.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

108 lines (94 loc) · 1.87 KB

 master

/

clocks2.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

108 lines (94 loc) · 1.87 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

/*

ID: xieke.b1

PROG: clocks

LANG: C++

*/

#include <iostream>

#include <fstream>

#include <string>

#include <vector>

#include <string.h>

#include <queue>

using namespace std;

ofstream fout("clocks.out");

ifstream fin ("clocks.in");

//int s[9];

vector<int> start;

vector<int> final;

const int MAXN = 1200000;

int vis[MAXN];

string dir[10]={

"",

"ABDE",

"ABC",

"BCEF",

"ADG",

"BDEFH",

"CFI",

"DEGH",

"GHI",

"EFHI"

};

int szs[10] = {

0,

4,3,4,3,5,3,4,3,4};

int compute(vector<int> &s){

int res = 0;

for(int i=0; i<9; i++){

res = res*4+s[i];

}

return res;

}

void print(vector<int> s){

for(int i=0; i<s.size(); i++){

cout<<s[i]<<" ";

}

cout<<endl;

}

typedef pair< vector<int> , string> mp;

void bfs(vector<int> s){

int tmp = compute(s);

vis[tmp] = 1;

queue<pair< vector<int> , string> > Q;

mp ns;

Q.push( mp(s, "") );

while(!Q.empty()){

ns = Q.front();

Q.pop();

if(ns.first==final){

cout<<ns.second<<endl;

for(int i=0; i<ns.second.size()-1; i++){

fout<<ns.second[i]<<" ";

}fout<<ns.second[ns.second.size()-1]<<endl;

return ;

}

for(int i=1; i<=9; i++){

int sz = szs[i];

vector<int> t= ns.first;

for(int j=0; j<sz; j++){

int pos = dir[i][j]-'A';

t[pos]+=1;

if(t[pos]==4)t[pos]=0;

}

int state = compute(t);

if( vis[state]==0){

Q.push( mp(t, ns.second+char('0'+i)) );

vis[state] = 1;

}

}

}

}

void work(){

bfs(start);

}

int main(){

for(int i=0; i<9; i++){

int t;

fin>>t;

start.push_back((t/3)%4);

final.push_back(0);

//fin>>s[i];

}

work();

return 0;

}