UVAOJ10047 | 哈喽哈咯

Written by razrlele 21:10 February 19, 2015

UVAOJ10047

据说是一道很经典的BFS题目。。。

因为要区分无效循环和正常遍历。。所以每个点除了xy坐标需要标记一下之外，还要标记轮子的方向和接地面的颜色。。。

然后注意到达终点的时候需要提前进行判断。。。不然要出大事。。。。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

/********************************************************

* File Name: uvaoj10047.cpp

* Author: razrLeLe

* Mail: razrlele@gmail.com

* Homepage: https://yueyu.io

* Created Time: Sun 15 Feb 2015 01:27:45 PM CST

******************************************************/

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#include "list"

#include "stack"

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

const int maxn = 30;

int M, N;

int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

char grid[maxn][maxn];

bool vis[maxn][maxn][4][5];

int x, y, xx, yy;

bool reachable;

int ans;

struct node

{

int x, y;

int color;

int c;

int dir;

}now, next;

queue<node> Q;

bool isOk(int a, int b)

{

return a >= 0 && a < M && b >= 0 && b < N;

}

void BFS()

{

while(!Q.empty())

{

now = Q.front();

Q.pop();

int i;

switch(now.dir)

{

case 0: i = 0;break;

case 1: i = 1;break;

case 2: i = 2;break;

case 3: i = 3;break;

}

int a = now.x+dir[i][0], b = now.y+dir[i][1];

int nextcolor = (now.color+1)%5;

if(isOk(a, b))

if(!vis[a][b][now.dir][nextcolor] && (grid[a][b] == '.' || grid[a][b] == 'T' || grid[a][b] == 'S'))

{

next.x = a;

next.color = nextcolor;

next.y = b;

next.dir = now.dir;

next.c = now.c + 1;

if(a == xx && b == yy && nextcolor == 0)

{

reachable = true;

ans = next.c;

return ;

}

vis[a][b][now.dir][nextcolor] = true;

Q.push(next);

}

int l = now.dir+1;

if(l > 3)

l = 0;

int r = now.dir-1;

if(r < 0)

r = 3;

if(!vis[now.x][now.y][r][now.color])

{

next.x = now.x;

next.y = now.y;

next.color = now.color;

next.c = now.c+1;

next.dir = r;

vis[next.x][next.y][r][now.color]=true;

Q.push(next);

}

if(!vis[now.x][now.y][l][now.color])

{

next.x = now.x;

next.y = now.y;

next.color = now.color;

next.c = now.c+1;

next.dir = l;

vis[next.x][next.y][l][now.color]=true;

Q.push(next);

}

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

int numcase = 0;

while(scanf("%d %d", &M, &N) && M && N)

{

reachable = false;

memset(grid, '#', sizeof(grid));

memset(vis, false, sizeof(vis));

getchar();

for(int i = 0; i < M; i++)

{

for(int j = 0; j < N; j++)

{

scanf("%c", &grid[i][j]);

if(grid[i][j] == 'S')

{

x = i;

y = j;

}

else if(grid[i][j] == 'T')

{

xx = i;

yy = j;

}

getchar();

}

while(!Q.empty())

Q.pop();

now.x = x;

now.y = y;

now.c = 0;

now.color = 0;

now.dir = 0;//0:N 1:W 2:S 3:E

vis[now.x][now.y][now.c][now.color] = true;

Q.push(now);

BFS();

if(numcase)

printf("\n");

printf("Case #%d\n", ++numcase);

if(reachable)

printf("minimum time = %d sec\n", ans);

else

printf("destination not reachable\n");

}

return 0;

}