-
Notifications
You must be signed in to change notification settings - Fork 0
/
00614.cpp
100 lines (89 loc) · 2.5 KB
/
00614.cpp
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
#include <stdio.h>
#include <memory.h>
int n, m;
int rs, cs, rt, ct;
int maze[ 15 ][ 15 ];
int ans[ 15 ][ 15 ];
#define W 0
#define N 1
#define E 2
#define S 3
int mov[][2] = {{0,-1},{-1,0},{0,1},{1,0}};
bool dfs(int ra, int ca, int cnt)
{
ans[ra][ca] = cnt;
if ( ra==rt && ca==ct )
{
ans[ra][ca] = cnt;
return true;
}
else
{
for (int k = 0; k < 4; k++)
{
if ( maze[ra][ca] & (1<<k) ) continue;
int nr = ra + mov[k][0];
int nc = ca + mov[k][1];
if ( nr>=1 && nr<=n && nc>=1 && nc<=m && ans[nr][nc]==-1 )
if (dfs( nr, nc, cnt+1 ))
{
ans[ra][ca] = cnt;
return true;
}
}
ans[ra][ca] = -2;
return false;
}
}
void printBorder(int ren)
{
for (int j=1; j<=m; j++)
{
if ( j == 1 ) printf("+");
if ( maze[ren][j] & (1<<N) ) printf("---");
else printf(" ");
printf("+");
}
puts("");
}
int main()
{
int test = 1;
while ( scanf("%d %d %d %d %d %d",&n,&m,&rs,&cs,&rt,&ct), n || m || rs || cs || rt || ct )
{
memset( maze, 0, sizeof maze );
int a;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
{
if ( i == 1 ) maze[i][j] |= (1 << N), maze[i-1][j] |= (1 << S);
if ( i == n ) maze[i][j] |= (1 << S), maze[i+1][j] |= (1 << N);
if ( j == 1 ) maze[i][j] |= (1 << W), maze[i][j-1] |= (1 << E);
if ( j == m ) maze[i][j] |= (1 << E), maze[i][j+1] |= (1 << W);
scanf("%d",&a);
if ( a & 1 ) maze[i][j] |= (1 << E), maze[i][j+1] |= (1 << W);
if ( a & 2 ) maze[i][j] |= (1 << S), maze[i+1][j] |= (1 << N);
}
memset( ans, -1, sizeof ans );
dfs( rs, cs, 1 );
printf("Maze %d\n\n",test++);
for (int i=1; i<=n; i++)
{
printBorder( i );
for (int j=1; j<=m; j++)
{
if ( j==1 ) printf("|");
if ( ans[i][j] == -2 ) printf("???");
else if ( ans[i][j] == -1 ) printf(" ");
else printf("%3d",ans[i][j]);
if ( maze[i][j] & (1<<E) ) printf("|");
else printf(" ");
}
puts("");
}
printBorder( n+1 );
puts("");
puts("");
}
return 0;
}