CodeForces - 589J Cleaner Robot

J. Cleaner Robot

time limit per test2 seconds memory limit per test512 megabytes inputstandard input outputstandard output Masha has recently bought a cleaner robot, it can clean a floor without anybody’s assistance.

Schematically Masha’s room is a rectangle, consisting of w × h square cells of size 1 × 1. Each cell of the room is either empty (rePResented by character ‘.’), or occupied by furniture (represented by character ‘*’).

A cleaner robot fully occupies one free cell. Also the robot has a current direction (one of four options), we will say that it looks in this direction.

The algorithm for the robot to move and clean the floor in the room is as follows:

clean the current cell which a cleaner robot is in; if the side-adjacent cell in the direction where the robot is looking exists and is empty, move to it and go to step 1; otherwise turn 90 degrees clockwise (to the right relative to its current direction) and move to step 2. The cleaner robot will follow this algorithm until Masha switches it off.

You know the position of furniture in Masha’s room, the initial position and the direction of the cleaner robot. Can you calculate the total area of the room that the robot will clean if it works infinitely?

Input The first line of the input contains two integers, w and h (1 ≤ w, h ≤ 10) — the sizes of Masha’s room.

Next w lines contain h characters each — the description of the room. If a cell of a room is empty, then the corresponding character equals ‘.’. If a cell of a room is occupied by furniture, then the corresponding character equals ‘*’. If a cell has the robot, then it is empty, and the corresponding character in the input equals ‘U’, ‘R’, ‘D’ or ‘L’, where the letter represents the direction of the cleaner robot. Letter ‘U’ shows that the robot is looking up according to the scheme of the room, letter ‘R’ means it is looking to the right, letter ‘D’ means it is looking down and letter ‘L’ means it is looking to the left.

It is guaranteed that in the given w lines letter ‘U’, ‘R’, ‘D’ or ‘L’ occurs exactly once. The cell where the robot initially stands is empty (doesn’t have any furniture).

Output In the first line of the output print a single integer — the total area of the room that the robot will clean if it works infinitely.

Examples input 2 3 U.. .*. output 4 input 4 4 R… .**. .**. …. output 12 input 3 4 ***D ..*. *… output 6 Note In the first sample the robot first tries to move upwards, it can’t do it, so it turns right. Then it makes two steps to the right, meets a wall and turns downwards. It moves down, unfortunately tries moving left and locks itself moving from cell (1, 3) to cell (2, 3) and back. The cells visited by the robot are marked gray on the picture.

题意：一个打扫房间的机器人，有一个算法，要求计算，根据这个算法，最多能打扫多少个地方。该算法为： 1、走到该位置，如果该位置没有打扫，则打扫 2、如果前面方向没有家具，则向该方向走，并执行step1 3、如何该方向下一步有家具，则向右转90度，执行step2 分析：该题目根据题目中的算法，使用dfs进行搜索即可，判断该位置有没有家具，有家具则转向，没有家具则走到该步。主要在于一块砖最多能走多少次？因为根据该算法，肯定有一个循环走的路径在里面，所以要设置重复走过多少次作为终止条件。一开始设置的vis[x][y] > 2的时候结束，但卡到了第90组示例，设置到vis[x][y] >3就可以通过了。该程序数据比较小，所以用dfs不会超时。 代码如下：

#include <stdio.h> #include <string.h> char map[15][15]; int dira[4][2]={-1,0,0,1,1,0,0,-1}; int vis[15][15]; int n,m; int cnt; void dfs(int x,int y,int dir) { int px= x + dira[dir][0]; int py= y + dira[dir][1]; for(int i=1;i<=4 && map[px][py]=='*';i++) { dir = (dir+1)%4; px= x + dira[dir][0]; py= y + dira[dir][1]; } if(map[px][py]!='*') { if(vis[px][py]>3) return ; if(vis[px][py]==0) cnt++; vis[px][py]++; dfs(px,py,dir); } } int main() { int i,j; int s,e; while(~scanf("%d %d",&n,&m)) { memset(map,'*',sizeof(map)); memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { getchar(); for(j=1;j<=m;j++) { scanf("%c",map[i]+j); if(map[i][j]!='*' && map[i][j]!='.') { s=i;e=j; } } } int dir=0; switch(map[s][e]) { case 'U': dir=0;break; case 'R': dir=1;break; case 'D': dir=2;break; case 'L': dir=3;break; } cnt=1; vis[s][e]=1; dfs(s,e,dir); printf("%d\n",cnt); } return 0; }