一道ACM题，烦了很久，还是没有头绪，求大神解答！
http://acm.tju.edu.cn/toj/vcontest/showp9013_E.html
请各位用C++代码写下，可以共同讨论下思路，谢谢了。
[解决办法]
我写了下面的代码，还有点问题。
#include<stdio.h>
char grid[10][10];
int result[10][10];
void find_result(int in,int col,int row)
{
int i=1;
int j=in;
int temp=1;
int step;
while(i>=1&&i<=row&&j<=col&&j>=1)
{
if(grid[i][j]=='w')
{
result[i][j]=temp;
if( result[i][j-1]>0)
{
step=result[i][j];
temp=result[i][j-1];
break;
}
j--;
temp++;
}
if(grid[i][j]=='e')
{
result[i][j]=temp;
if( result[i][j+1]>0)
{
step=result[i][j];
temp=result[i][j+1];
break;
}
j++;
temp++;
}
if(grid[i][j]=='n')
{
result[i][j]=temp;
if( result[i-1][j]>0)
{
step=result[i][j];
temp=result[i-1][j];
break;
}
i--;
temp++;
}
if(grid[i][j]=='s')
{
result[i][j]=temp;
if( result[i+1][j]>0)
{
step=result[i][j];
temp=result[i+1][j];
break;
}
i++;
temp++;
}
}
if(i<1
[解决办法]
i>row
[解决办法]
j>col
[解决办法]
j<1)
{
printf("%d steps to exit\n",temp);
}
else
{
printf("%d steps before a loop of %d steps\n",temp,step-temp);
}
}
int main()
{
int row,col,in;
int i,j;
printf("please input the row ,col and in\n");
scanf("%d",&row);
scanf("%d",&row);
scanf("%d",&row);
printf("please input the grid\n");
getchar();
for(i=1;i<=row;i++)
{
scanf("%s",grid[i]);
}
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
result[i][j]=0;
}
}
find_result(in,col,row);
return 0;
}
[解决办法]
模拟一下整个过程就可以吧，
用和grid一样大小的数组travel[][]，记录移动的过程，
初始travel全部为零，
移动一步，在travel相应的位置记下是第几步，
如果这个位置不为零（假设k），则表示来过，用当前是第i步，减去k，就是循环的步数。
即循环是从k到i
其他的情况（从边界出来了）应该容易判断。
[解决办法]
这个题在ACM中被称为模拟题，只要模拟下题目要求就可以了。
楼主想练习ACM功力，就多做些动态规划的题目吧。
[解决办法]
代码如下：
#include<stdio.h>
static char grid[10][10];
static int result[10][10];
void find_result(int in,int col,int row)
{
int i=1;
int j=in-1;
int temp=1;
int step=0;
while(i>=1&&i<=row&&j<col&&j>=0)
{
result[i][j]=temp;
if(grid[i][j]=='w')
{
if( result[i][j-1]>0)
{
step=result[i][j];
temp=result[i][j-1];
break;
}
j--;
temp++;
}
if(grid[i][j]=='e')
{
if( result[i][j+1]>0)
{
step=result[i][j];
temp=result[i][j+1];
break;
}
j++;
temp++;
}
if(grid[i][j]=='n')
{
if( result[i-1][j]>0)
{
step=result[i][j];
temp=result[i-1][j];
break;
}
i--;
temp++;
}
if(grid[i][j]=='s')
{
if( result[i+1][j]>0)
{
step=result[i][j];
temp=result[i+1][j];
break;
}
i++;
temp++;
}
}
if(i<1
[解决办法]
i>row
[解决办法]
j>col
[解决办法]
j<1)
{
printf("%d steps to exit\n",temp-1);
}
else
{
printf("%d steps before a loop of %d steps\n",temp-2,step-temp+1);
}
}
int main()
{
int row,col,in;
int i,j;
printf("please input the row ,col and in\n");
scanf("%d",&row);
scanf("%d",&col);
scanf("%d",&in);
printf("please input the grid\n");
for(i=1;i<=row;i++)
{
scanf("%s",grid[i]);
}
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
{
result[i][j]=0;
}
}
find_result(in,col,row);
return 0;
}
