POJ-1573 解题报告

题意简述

一个机器人从指定位置进入一个每格都指向一个确定方向的矩阵。它会顺着格子给定的方向运动。

若机器人能走出矩阵,则输出其经过的格子数量。

若机器人会陷入一个环,则输出经过多少格后,机器人进入了一个格数为多少的环。

算法分析

与POJ-2632类似。直接模拟。

建立一个等大的累加矩阵,存储机器人经过的次数。当机器人碰墙时则认为机器人走出矩阵。计算此时累加矩阵内1的个数。即为经过格子数量。

当机器人到达的点的累加值已经达到2,则说明机器人已经过一个环两次。此时计算累加矩阵内1的个数,即进入环前经过的格子数;计算矩阵内2的个数,即环所占格子数。

Problem Status: AC。时间0ms,内存120k

——————————————————————分割线——————————————————————

优化:

没想到。POJ排名第一仍然是0ms 4k的恐怖数据……

程序样例


[c]
#include<stdio.h>

void out(int map[][20],int n,int r,int c)
{
int i,j,ans1=0,ans2=0;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
if(map[i][j]==1) ans1++;
if(map[i][j]==2) ans2++;
}
if (n==1)
printf("%d step(s) to exitn",ans1);
if (n==2)
printf("%d step(s) before a loop of %d step(s)n",ans1,ans2);
}

int main()
{
int r,c,i,j,pos[2],b[20][20],flag;
char map[20][20],tem[20];
while(scanf("%d%d%d",&r,&c,&pos[1]),!(r==0&&c==0&&pos[1]==0))
{
pos[0]=0; pos[1]–;
for(i=0;i<r;i++)
{
scanf("%s",tem);
for(j=0;j<c;j++)
{
b[i][j]=0;
map[i][j]=tem[j];
}
}
flag=1;
while(flag)
{
b[pos[0]][pos[1]]++;
switch(map[pos[0]][pos[1]])
{
case ‘N’:pos[0]–; break;
case ‘W’:pos[1]–; break;
case ‘S’:pos[0]++; break;
case ‘E’:pos[1]++; break;
}
if(pos[0]>=0&&pos[0]<r&&pos[1]>=0&&pos[1]<c){
if(b[pos[0]][pos[1]]==2)
{
out(b,2,r,c);
flag=0;
}}
else
{
out(b,1,r,c);
flag=0;
}
}
}
}

[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *