NO IMAGE

題目:

A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are 

N north (up the page) 
S south (down the page) 
E east (to the right on the page) 
W west (to the left on the page) 

For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid. 

Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop through 8 instructions, and never exits. 

You are to write a program that determines how long it takes a robot to get out of the grid or how the robot loops around. 

Input

There will be one or more grids for robots to navigate. The data for each is in the following form. On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in the grid, and the number of the column in which the robot enters from the north. The possible entry columns are numbered starting with one at the left. Then come the rows of the direction instructions. Each grid will have at least one and at most 10 rows and columns of instructions. The lines of instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a row containing 0 0 0. 

Output

For each grid in the input there is one line of output. Either the robot follows a certain number of instructions and exits the grid on any one the four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions on some number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word “step” is always immediately followed by “(s)” whether or not the number before it is 1. 

Sample Input

3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 

Sample Output

10 step(s) to exit
3 step(s) before a loop of 8 step(s)

題目大意:

    機器人會按照地板的字母代表的方向前進,要計算的是它經過多少步走出去或者進入一個環中。

解題思路:

    用遞迴求解,結束條件設定為走出區域或走到曾經走到過的地板。在做這道題時我用map儲存機器人走過的路線,map的第一維是結構體,裡面是座標。要注意的是給結構體過載小於號時如果隨意過載(比如只是用x座標作比較),那麼map會認為x相同的兩個結構體就是相同的,這樣在查詢的時候就可能出錯,因為這道題地板範圍只有10,所以我用20*x y作為比較,可以保證不同的x和y和組合一定有不同的比較值。

程式碼:

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring> 

using namespace std;

struct node{
    int x,y;
    bool operator <(node const& n)const{
        return 20*x y<20*n.x n.y;
    }
    node(int a,int b){
        x=a;
        y=b;
    }
};

int h,l,k;
char ca[12][12]={‘\0’};
map<node,int > ma;

void f(int a,int b,int step){
    map<node,int>::iterator it;
    if(a<0||b<0||a>=h||b>=l){
        cout<<step<<” step(s) to exit”<<endl;
    }else if((it=ma.find(node(a,b)))!=ma.end()){
        cout<<it->second<<” step(s) before a loop of “<<step-it->second<<” step(s)”<<endl;
    }else{
        node cu(a,b);
        ma.insert(pair<node,int>(cu,step)); 
        if(ca[a][b]==’S’)f(a 1,b,step 1);
        else if(ca[a][b]==’N’)f(a-1,b,step 1);
        else if(ca[a][b]==’E’)f(a,b 1,step 1);
        else f(a,b-1,step 1);
    }
}

int main(){
    while(scanf(“%d %d %d”,&h,&l,&k)){
        if(h==0)break;
        ma.clear();
        memset(ca,’\0′,sizeof(ca));
        for(int i=0;i<h;i )scanf(“%s”,ca[i]); 
        f(0,k-1,0);
    }
    return 0;
}