The Philosophy of Searching

FIRST:

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
#include <stdio.h>
#include <queue>
using namespace std;
bool mark[50][50][50];
int maze[50][50][50];
struct N
{
int x,y,z;
int t;
};

queue<N> Q;
int go[][3]={
//坐标变换数组
//(x,y,z)=> (x+go[i][0],y+go[i][1],z+go[i][2])
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1
};

int BFS(int a,int b, int c)
{
while(Q.empty()==false)
{
N now=Q.front();
Q.pop();
for(int i=0;i<6;i++)
{
int nx=now.x+go[i][0];
int ny=now.y+go[i][1];
int nz=now.z+go[i][2];
if(nx<0||nx>=a||ny<0||ny>=b||nz<0||nz>=c) continue;

if(maze[nx][ny][nz]==1) continue;
if(mark[nx][ny][nz]==true) continue;

N temp;
temp.x=nx;
temp.y=ny;
temp.z=nz;
temp.t=now.t+1;
Q.push(temp);
mark[nx][ny][nz]=true;

if(nx==a-1&&ny==b-1&&nz==c-1) return temp.t;
}
}
return -1;
}

int main()
{
int T;
// printf("%d",Q.empty());
scanf("%d",&T);
while(T--)
{
int a,b,c,t;
scanf("%d%d%d%d",&a,&b,&c,&t);

for(int i=0;i<a;i++)
{
for(int j=0;j<b;j++)
{
for(int k=0;k<c;k++)
{
scanf("%d",&maze[i][j][k]);
mark[i][j][k]=false;
}
}
}

while(Q.empty()==false) Q.pop();
mark[0][0][0]=true;
N temp;
temp.t=temp.y=temp.x=temp.z=0;
Q.push(temp);
int rec=BFS(a,b,c);
if(rec<=t) printf("%d\n",rec);
else printf("-1\n");
}
return 0;
}

SECOND:

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
#include <stdio.h>
#include <string.h>

int ans[22];
bool hash[22];
int n;
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};

bool judge(int x)
{
for(int i=0;i<13;i++)
{
if(prime[i]==x) return true;
}
return false;
}

void check()
{
if(judge(ans[n]+ans[1])==false) return;
for(int i=1;i<=n;i++)
{
if(i!=1) printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}

void DFS(int num) //当前放入环中的数字
{
if(num>1)
{
if(judge(ans[num]+ans[num-1])==false) return ;
}
if(num==n) //已经放入了n个数
{
check();
return ;
}
for(int i=2;i<=n;i++)
{
if(hash[i]==false)
{
hash[i]=true;
ans[num+1]=i;
DFS(num+1);
hash[i]=false;
}
}
}

int main()
{
int cas=0;
while(scanf("%d",&n)!=EOF)
{
cas++;
for(int i=0;i<22;i++) hash[i]=false;
ans[1]=1;
printf("Case %d:\n",cas);
hash[1]=true;
DFS(1);
printf("\n");
}
return 0;
}