UVa 556 Amazing

题目描述

题目要求模拟一个机器人沿着右墙法则在迷宫中行走。机器人从西南角（左下角）出发，初始方向朝东。机器人保持右侧始终贴着墙壁，若前方有墙则向左转，直到可以前进。机器人回到起点时停止。统计每个单元格被访问的次数（000、111、222、333、444次），输出五个数字。

输入格式

输入包含多个迷宫。每个迷宫的第一行包含两个整数bbb和www（行数和列数）。接下来bbb行，每行www个字符，0表示空地，1$ 表示墙。输入以0 0` 结束。

输出格式

对于每个迷宫，输出一行五个整数，分别表示被访问000、111、222、333、444次的单元格数量，每个整数右对齐宽度333。

样例

输入

3 5 01010 01010 00000 0 0

输出

2 3 5 1 0

题目分析

本题的核心是模拟机器人行走，按右墙法则。

方向与转向

• 方向：东(000)、南(111)、西(222)、北(333)。
• 右转：方向d=(d+3) mod 4d = (d + 3) \bmod 4d=(d+3)mod4（逆时针909090度）。
• 左转：方向d=(d+1) mod 4d = (d + 1) \bmod 4d=(d+1)mod4。

行走规则

• 尝试前进（当前方向）。若前方为空地，则移动；否则左转（逆时针）重复尝试。
• 移动后，检查右侧（当前方向右转909090度）是否为空地，若是则右转（即调整方向为右侧方向）。

边界

迷宫四周有墙，但输入不包含外边界，需要自行处理边界检查。

统计

记录每个单元格被访问的次数，起点在第一次离开时计数？注意定义：正方形被访问是指机器人进入并离开它。初始位置算访问吗？从样例推断，初始位置算一次访问。

复杂度分析

机器人移动步数有限，最多访问每个单元格多次，直至回到起点。

代码实现

// Amazing// UVa ID: 556// Verdict: Accepted// Submission Date: 2016-08-18// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intb,w;chargrid[100][100];intcounter[100][100];intoffset[4][2]={{0,1},{1,0},{0,-1},{-1,0}};intrightside[4][2]={{-1,0},{0,1},{1,0},{0,-1}};while(cin>>b>>w,b){memset(counter,0,sizeof(counter));for(inti=1;i<=b;i++)for(intj=1;j<=w;j++)cin>>grid[b-i+1][j];intx=1,y=1,nextx,nexty,rightx,righty,d=0;do{nextx=x+offset[d][0],nexty=y+offset[d][1];if(nextx<1||nextx>b||nexty<1||nexty>w||grid[nextx][nexty]=='1'){d++;d%=4;}else{counter[nextx][nexty]++;x=nextx,y=nexty;rightx=nextx+rightside[d][0],righty=nexty+rightside[d][1];if(rightx>=1&&rightx<=b&&righty>=1&&righty<=w&&grid[rightx][righty]=='0'){d+=3;d%=4;}}}while(x!=1||y!=1);inttimes[5]={0,0,0,0,0};for(inti=1;i<=b;i++)for(intj=1;j<=w;j++)if(grid[i][j]=='0')times[counter[i][j]]++;for(inti=0;i<=4;i++)cout<<setw(3)<<times[i];cout<<'\n';}return0;}