| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
模拟+bfs(贴左右墙走的代码可以合并~)#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
const int N = 40 + 5;
int size_x, size_y;
int st_x, st_y, end_x, end_y;
char map[N][N];
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { -1, 0, 1, 0 };
int queue[N * N], step[N][N];
bool pd[N][N];
#define rotate(p,dir) ((p + dir + 4) % 4)
int go(int dir) // -1-left, 1-right
{
int p, cnt = 0;
if (st_x - 1 >= 0 && st_x - 1 < size_x && map[st_x - 1][st_y] == '#')
p = (st_y == 0 ? 2 : 0);
else p = (st_x == 0 ? 1 : 3);
int x = st_x, y = st_y;
while (x != end_x || y != end_y)
{
while (map[y + dy[p]][x + dx[p]] == '#')
p = rotate(p, -dir);
x += dx[p]; y += dy[p]; cnt++;
if (map[y + dy[rotate(p, dir)]][x + dx[rotate(p, dir)]] != '#')
p = rotate(p, dir);
}
return cnt + 1;
}
#define ok(x,y) (x >= 0 && x < size_x && y >= 0 && y < size_y)
int bfs()
{
int l = 0, r = 0;
memset(pd, false, sizeof(pd));
step[st_x][st_y] = 1;
queue[r++] = st_x * size_x + st_y;
while (l < r)
{
int p = queue[l++];
for (int i = 0; i < 4; i++)
{
int x = p / size_x, y = p % size_x;
int x1 = x + dx[i], y1 = y + dy[i];
if (!pd[x1][y1] && ok(x1, y1) && map[y1][x1] != '#')
{
queue[r++] = x1 * size_x + y1; pd[x1][y1] = true;
step[x1][y1] = step[x][y] + 1;
if (x1 == end_x && y1 == end_y)
return step[x1][y1];
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d\n", &size_x, &size_y);
for (int i = 0; i < size_y; i++)
{
gets(map[i]);
for (int j = 0; j < size_x; j++)
if (map[i][j] == 'S') st_x = j, st_y = i;
else if (map[i][j] == 'E') end_x = j, end_y = i;
}
printf("%d %d %d\n", go(-1), go(1), bfs());
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator