Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

题解:

Posted by jwzxgo at 2012-03-14 22:28:24 on Problem 1573
只要注意这个情况就OK: 0 step(s) before a loop of 2 step(s)
数据大小都如题所述。

代码如下:http://ideone.com/1cNje

#include <stdio.h>
#include <assert.h>
 
char direction[11][11]; // reserve one space for \0
int history[10][10];
int maxx, maxy, starty;
int step;
void init(){
        int i=0, j=0;
        for(i=0; i<10; i++){ for(j=0;j<10;j++){ history[i][j]=0; } }
        // 0: not visited yet 
}
void cal(){
        step = 0;
        int x = 0, y = starty -1; // grid start from 0 in prog
        while(1){
                if( x<0 || y<0 || x>=maxx || y>= maxy ){ 
                        printf("%d step(s) to exit\n", step);
                        return;
                }else if( history[x][y] != 0 ){
                        printf("%d step(s) before a loop of %d step(s)\n", history[x][y]-1, step - history[x][y]+1);
                        return;
                }else{
                        // still in the box
                        step += 1;
                        history[x][y] = step;
                        switch( direction[x][y] ){
                        case 'W': y--; break;
                        case 'E': y++; break;
                        case 'N': x--; break;
                        case 'S': x++; break;
                        default: assert( 0&& "Unknown charactor!" );
                        }
                }
                
        }
}
int main(void) {
        while(1){
                scanf("%d%d%d", &maxx, &maxy, &starty);
                if( maxy == 0 ){ // normal lines : maxy >=1
                        assert( maxx == 0 && starty == 0 );
                        return 0; 
                }else{
                        int i=0;
                        for(i=0; i<maxx; i++){
                                scanf("%s", direction[i]);
                        }
                        init();
                        cal();
                }
        }
        return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator