1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 char map[21][21];
7 int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
8 bool hash[21][21][10000];
9 struct man{
10 int x,y;
11 bool key[10];
12 int t;
13 };
14 int si,sj,ei,ej;
15 int n,m,t;
16 bool succ;
17 queue<man>zero;
18 int main()
19 {
20 int i,j,k,ti;
21 int hh,hh2;
22 man head,p;
23 while(scanf("%d%d%d",&n,&m,&t)!=EOF)
24 {
25 memset(map,0,sizeof(map));
26 memset(hash,0,sizeof(hash));
27 for(i=0;i<n;i++)
28 {
29 scanf("%s",map[i]);
30 for(j=0;j<m;j++)
31 {
32 if(map[i][j]=='@')
33 {
34 hash[i][j][0]=1;
35 si=i;
36 sj=j;
37 map[i][j]='.';
38 }
39 if(map[i][j]=='^')
40 {
41 ei=i;
42 ej=j;
43 map[i][j]='.';
44 }
45 }
46 }
47 head.t=0;
48 head.x=si;
49 head.y=sj;
50 memset(head.key,0,sizeof(head.key));
51 while(!zero.empty())
52 zero.pop();
53 zero.push(head);
54 succ=0;
55 ti=99999;
56 while(!zero.empty())
57 {
58 head=zero.front();
59 zero.pop();
60 if(head.t==t)
61 {
62 if(head.x==si&&head.y==sj)
63 {
64 head.t=0;
65 hh2=0;
66 for(int jj=0;jj<10;jj++)
67 {
68 if(head.key[jj])
69 hh2+=1<<(jj);
70 }
71 if(hash[si][sj][hh2]==0)
72 {
73 hash[si][sj][hh2]=1;
74 zero.push(head);
75 }
76 continue;
77 }else
78 continue;
79 }
80 if(head.x==ei&&head.y==ej)
81 {
82 if(head.t<t)
83 {
84 succ=1;
85 ti=head.t;
86 break;
87 }else
88 continue;
89 }
90 int x,y;
91 for(i=0;i<4;i++)
92 {
93 x=dir[i][0]+head.x;
94 y=dir[i][1]+head.y;
95 if(x>=n||y>=m||x<0||y<0||map[x][y]=='*')
96 continue;
97 hh=0;
98 for(int jj=0;jj<10;jj++)
99 {
100 if(head.key[jj])
101 hh+=1<<(jj);
102 p.key[jj]=head.key[jj];
103 }
104 if(map[x][y]=='.'&&hash[x][y][hh]==0)
105 {
106 p.x=x;
107 p.y=y;
108 p.t=head.t+1;
109 hash[x][y][hh]=1;
110 if(p.t<t||(p.t==t&&p.x==si&&p.y==sj))
111 zero.push(p);
112 }
113 if(map[x][y]>='a'&&map[x][y]<='j')
114 {
115 if(head.key[map[x][y]-'a']&&hash[x][y][hh]==0)
116 {
117 p.x=x;
118 p.y=y;
119 p.t=head.t+1;
120 hash[x][y][hh]=1;
121 if(p.t<t||(p.t==t&&p.x==si&&p.y==sj))
122 zero.push(p);
123 }
124 else if(!head.key[map[x][y]-'a']&&hash[x][y][hh+1<<(map[x][y]-'a')]==0)
125 {
126 p.key[map[x][y]-'a']=1;
127 hh+=1<<(map[x][y]-'a');
128 hash[x][y][hh]=1;
129 p.x=x;
130 p.y=y;
131 p.t=head.t+1;
132 if(p.t<t||(p.t==t&&p.x==si&&p.y==sj))
133 zero.push(p);
134 }
135 }
136 if(map[x][y]>='A'&&map[x][y]<='J'&&hash[x][y][hh]==0&&head.key[map[x][y]-'A'])
137 {
138 hash[x][y][hh]=1;
139 p.x=x;
140 p.y=y;
141 p.t=head.t+1;
142 if(p.t<t||(p.t==t&&p.x==si&&p.y==sj))
143 zero.push(p);
144 }
145 }
146 }
147 if(succ)
148 printf("%d\n",ti);
149 else
150 printf("-1\n");
151 }
152 }
153
154
posted on 2009-02-21 19:29
混沌的云 閱讀(473)
評論(2) 編輯 收藏 引用