首页 > 代码库 > CodeForces 589J Cleaner Robot
CodeForces 589J Cleaner Robot
有一个M*N的矩阵,有一个会自动清洁的机器人,这个机器人会按照设定好的程序来打扫卫生,如果当前方向前面可以行走,那么直接走,如果不可以走那么会向右转动90度,然后回归上一步判断。求机器人最多能打扫的面积是多少
一开始认为是走到之前清扫过的就停止搜索 后来知道是走到一个四个方向都走过的点才停止搜索
#include<stdio.h> #include<string.h> const int MAXN = 17; ///‘U‘, ‘R‘, ‘D‘ ‘L‘ int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; //后面是前面90度 int M, N; char G[MAXN][MAXN]; bool v[MAXN][MAXN][4]; void DFS(int k, int x, int y, int &ans) //k纪录当前方向 { if(G[x][y] == ‘.‘) { ans += 1; G[x][y] = ‘#‘; } for(int i=0; i<4; i++) { int nx = x+dir[(i+k)%4][0]; int ny = y+dir[(i+k)%4][1]; if(nx>=0&&nx<M && ny>=0&&ny<N && G[nx][ny]!=‘*‘) { if(v[nx][ny][(i+k)%4] == true) break; v[nx][ny][(i+k)%4] = true; DFS((i+k)%4, nx, ny, ans); break; } } } int main() { while(scanf("%d%d", &M, &N) != EOF) { memset(v, 0, sizeof(v)); int x, y, op; for(int i=0; i<M; i++) { scanf("%s", G[i]); for(int j=0; j<N; j++) { if(G[i][j] == ‘U‘) op = 0, x=i, y=j; if(G[i][j] == ‘R‘) op = 1, x=i, y=j; if(G[i][j] == ‘D‘) op = 2, x=i, y=j; if(G[i][j] == ‘L‘) op = 3, x=i, y=j; } } int ans = 1; DFS(op, x, y, ans); printf("%d\n", ans); } return 0; }
CodeForces 589J Cleaner Robot
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。