有一个M*N的矩阵,有一个会自动清洁的机器人,这个机器人会按照设定好的程序来打扫卫生,如果当前方向前面可以行走,那么直接走,如果不可以走那么会向右转动90度,然后回归上一步判断。求机器人最多能打扫的面积是多少。
分析:直接搜就行了.......
代码如下:
----------------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<string.h> const int MAXN = ; ///'U', 'R', 'D' 'L'
int dir[][] = { {-,},{,},{,},{,-} };
int M, N;
char G[MAXN][MAXN];
bool v[MAXN][MAXN][]; void DFS(int k, int x, int y, int &ans)
{
if(G[x][y] == '.')
{
ans += ;
G[x][y] = '#';
} for(int i=; i<; i++)
{
int nx = x+dir[(i+k)%][];
int ny = y+dir[(i+k)%][]; if(nx>=&&nx<M && ny>=&&ny<N && G[nx][ny]!='*')
{
if(v[nx][ny][(i+k)%] == true)
break;
v[nx][ny][(i+k)%] = true;
DFS((i+k)%, nx, ny, ans);
break;
}
}
} int main()
{
while(scanf("%d%d", &M, &N) != EOF)
{
memset(v, , sizeof(v)); int x, y, op; for(int i=; i<M; i++)
{
scanf("%s", G[i]);
for(int j=; j<N; j++)
{
if(G[i][j] == 'U')
op = , x=i, y=j;
if(G[i][j] == 'R')
op = , x=i, y=j;
if(G[i][j] == 'D')
op = , x=i, y=j;
if(G[i][j] == 'L')
op = , x=i, y=j;
}
} int ans = ;
DFS(op, x, y, ans); printf("%d\n", ans);
} return ;
}