Poj OpenJudge 百练 1573 Robot Motion

1.Link:

http://poj.org/problem?id=1573

http://bailian.openjudge.cn/practice/1573/

2.Content:

3.Method:

模拟题，使用arr_mark保存行走路径，走到重复的路则为loop，出边界则为exit

特别注意 0 step(s) before a loop of 4 step(s) 的情况

如：

4.Code:

 #include <iostream>

 #include <cstring>

 using namespace std;

 //N,E,S,W

 const int idx_x[] = {,,,-};

 const int idx_y[] = {-,,,};

 const char idx_ch[] = {'N','E','S','W'};

 const int num_d = ;

 int main()

 {

     //freopen("D://input.txt","r",stdin);

     int y,x;

     int i;

     int w,h,s;

     cin >> h >> w >> s;

     while(h !=  || w !=  || s != )

     {

         int **arr_d = new int*[h];

         for(y = ; y < h; ++y) arr_d[y] = new int[w];

         char ch;

         for(y = ; y < h; ++y)

         {

             for(x = ; x < w; ++x)

             {

                 cin >> ch;

                 for(i = ; i < num_d; ++i) if(idx_ch[i] == ch) break;

                 arr_d[y][x] = i;

             }

         }

         //for(y = 0; y < h; ++y)

         //{

         //    for(x = 0; x < w; ++x)

         //    {

         //        cout << arr_d[y][x] << " ";

         //    }

         //    cout << endl;

         //}

         int **arr_mark = new int*[h];

         for(y = ; y < h; ++y)

         {

             arr_mark[y] = new int[w];

             memset(arr_mark[y],,sizeof(int) * w);

         }

         y = ;

         x = s - ;

         int path = ;

         int nx,ny;

         while(!arr_mark[y][x])//loop

         {

             nx = x;

             ny = y;

             arr_mark[y][x] = ++path;

             x = nx + idx_x[arr_d[ny][nx]];

             y = ny + idx_y[arr_d[ny][nx]];

             if(y <  || y >= h || x <  || x >= w) break;//exit

         }

         if(y <  || y >= h || x <  || x >=w)

         {

             cout << path << " step(s) to exit" << endl;

         }

         else

         {

             cout << (arr_mark[y][x] - ) << " step(s) before a loop of " << (arr_mark[ny][nx] - arr_mark[y][x] + ) << " step(s)" << endl;

         }

         //for(y = 0; y < h; ++y)

         //{

         //    for(x = 0; x < w; ++x) cout << arr_mark[y][x] << " ";

         //    cout << endl;

         //}

         for(y = ; y < h; ++y) delete [] arr_mark[y];

         delete [] arr_mark;

         for(y = ; y < h; ++y) delete [] arr_d[y];

         delete [] arr_d;

         cin >> h >> w >> s;

     }

     //fclose(stdin);

     return ;

 }

5.Reference:

http://poj.org/showmessage?message_id=123463