| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
题解:
只要注意这个情况就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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator