One of our delivery robots is malfunctioning! The job of the robot is simple; it should follow a list of instructions in order to reach a target destination. The list of instructions is originally correct to get the robot to the target. However, something is going wrong as we upload the instructions into the robot’s memory. During the upload, one random instruction from the list takes on a different value than intended. Yes, there is always a single bad instruction in the robot’s memory and it always results in the robot arriving at an incorrect destination as it finishes executing the list of instructions.

The robot can execute the instructions “<tt class="ttfamily">Left</tt>”, “<tt class="ttfamily">Right</tt>”, and “<tt class="ttfamily">Forward</tt>”. The “<tt class="ttfamily">Left</tt>” and “<tt class="ttfamily">Right</tt>” instructions do not result in spatial movement but result in a 9090-degree turn in the corresponding direction. “<tt class="ttfamily">Forward</tt>” is the only instruction that results in spatial movement, causing the robot to move one unit in the direction it is facing. The robot always starts at the origin (0,0)(0,0) of a grid and faces north along the positive y-axis.

Given the coordinates of the target destination and the list of instructions that the robot has in its memory, you are to identify a correction to the instructions to help the robot reach the proper destination.

Input

The first line of the input contains the xx and yy integer coordinates of the target destination, where 50x50−50≤x≤50 and 50y50−50≤y≤50. The following line contains an integer nn representing the number of instructions in the list, where 1n501≤n≤50. The remaining nn lines each contain a single instruction. These instructions may be: “<tt class="ttfamily">Left</tt>”, “<tt class="ttfamily">Forward</tt>”, or “<tt class="ttfamily">Right</tt>”.

Output

Identify how to correct the robot’s instructions by printing the line number (starting at 11) of an incorrect input instruction, followed by an instruction substitution that would make the robot reach the target destination. If there are multiple ways to fix the instructions, report the fix that occurs for the earliest line number in the sequence of instructions. There is always exactly one unique earliest fix.

Sample Input 1 Sample Output 1
3 2
11
Forward
Right
Forward
Forward
Left
Forward
Forward
Left
Forward
Right
Forward
8 Right
Sample Input 2 Sample Output 2
-1 1
3
Right
Left
Forward
1 Forward

 

题解:给一个指定的点,给机器人下指令,前进、向右或者向左转,然后机器人出了故障,中间有一个命令出错了(可能有多种解决方案,输出最早的),找到第几个出错,并输出正确指令。

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<string>
  9 using namespace std;
 10 int x, y;
 11 int n;
 12 char ins[500][10];
 13 int map[1][2] = {0};
 14 int go[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
 15 int main()
 16 {
 17     int turn = 0;
 18     scanf("%d %d", &x, &y);
 19     scanf("%d", &n);
 20     for (int i = 1; i <= n; i++)
 21     {
 22         scanf("%s", ins[i]);
 23     }
 24     for (int i = 1; i <= n; i++)
 25     {
 26         if (strcmp(ins[i], "Forward") == 0)
 27         {
 28             strcpy(ins[i],"Right");
 29             turn = 0;
 30             for (int j = 1; j <= n; j++)
 31             {
 32                 if (strcmp(ins[j], "Forward") == 0)
 33                 {
 34                     map[0][0] += go[turn][0];           //y
 35                     map[0][1] += go[turn][1];         //x
 36                 }
 37                 else if (strcmp(ins[j], "Right") == 0)
 38                 {
 39                     turn++;
 40                     if (turn > 3) turn = 0;
 41                 }
 42                 else
 43                 {
 44                     turn--;
 45                     if (turn < 0) turn = 3;
 46                 }
 47             }
 48             if (map[0][0] == y&&map[0][1] == x)
 49             {
 50                 printf("%d %s\n", i, ins[i]);
 51                 break;
 52             }
 53             map[0][0] = 0;
 54             map[0][1] = 0;
 55             strcpy(ins[i], "Left");
 56             turn = 0;
 57             for (int j = 1; j <= n; j++)
 58             {
 59                 if (strcmp(ins[j], "Forward") == 0)
 60                 {
 61                     map[0][0] += go[turn][0];           //y
 62                     map[0][1] += go[turn][1];         //x
 63                 }
 64                 else if (strcmp(ins[j], "Right") == 0)
 65                 {
 66                     turn++;
 67                     if (turn > 3) turn = 0;
 68                 }
 69                 else
 70                 {
 71                     turn--;
 72                     if (turn < 0) turn = 3;
 73                 }
 74             }
 75             if (map[0][0] == y&&map[0][1] == x)
 76             {
 77                 printf("%d %s\n", i, ins[i]);
 78                 break;
 79             }
 80             strcpy(ins[i], "Forward");
 81             map[0][0] = 0;
 82             map[0][1] = 0;
 83         }
 84         else if (strcmp(ins[i], "Right") == 0)
 85         {
 86 
 87             strcpy(ins[i], "Forward");
 88             turn = 0;
 89             for (int j = 1; j <= n; j++)
 90             {
 91                 if (strcmp(ins[j], "Forward") == 0)
 92                 {
 93                     map[0][0] += go[turn][0];           //y
 94                     map[0][1] += go[turn][1];         //x
 95                 }
 96                 else if (strcmp(ins[j], "Right") == 0)
 97                 {
 98                     turn++;
 99                     if (turn > 3) turn = 0;
100                 }
101                 else
102                 {
103                     turn--;
104                     if (turn < 0) turn = 3;
105                 }
106             }
107             if (map[0][0] == y&&map[0][1] == x)
108             {
109                 printf("%d %s\n", i, ins[i]);
110                 break;
111             }
112             map[0][0] = 0;
113             map[0][1] = 0;
114             strcpy(ins[i], "Left");
115             turn = 0;
116             for (int j = 1; j <= n; j++)
117             {
118                 if (strcmp(ins[j], "Forward") == 0)
119                 {
120                     map[0][0] += go[turn][0];           //y
121                     map[0][1] += go[turn][1];         //x
122                 }
123                 else if (strcmp(ins[j], "Right") == 0)
124                 {
125                     turn++;
126                     if (turn > 3) turn = 0;
127                 }
128                 else
129                 {
130                     turn--;
131                     if (turn < 0) turn = 3;
132                 }
133             }
134             if (map[0][0] == y&&map[0][1] == x)
135             {
136                 printf("%d %s\n", i, ins[i]);
137                 break;
138             }
139             strcpy(ins[i], "Right");
140             map[0][0] = 0;
141             map[0][1] = 0;
142         }
143         else
144         {
145             
146             strcpy(ins[i], "Right");
147             turn = 0;
148             for (int j = 1; j <= n; j++)
149             {
150                 if (strcmp(ins[j], "Forward") == 0)
151                 {
152                     map[0][0] += go[turn][0];           //y
153                     map[0][1] += go[turn][1];         //x
154                 }
155                 else if (strcmp(ins[j], "Right") == 0)
156                 {
157                     turn++;
158                     if (turn > 3) turn = 0;
159                 }
160                 else
161                 {
162                     turn--;
163                     if (turn < 0) turn = 3;
164                 }
165             }
166             if (map[0][0] == y&&map[0][1] == x)
167             {
168                 printf("%d %s\n", i, ins[i]);
169                 break;
170             }
171             map[0][0] = 0;
172             map[0][1] = 0;
173             strcpy(ins[i], "Forward");
174             turn = 0;
175             for (int j = 1; j <= n; j++)
176             {
177                 if (strcmp(ins[j], "Forward") == 0)
178                 {
179                     map[0][0] += go[turn][0];           //y
180                     map[0][1] += go[turn][1];         //x
181                 }
182                 else if (strcmp(ins[j], "Right") == 0)
183                 {
184                     turn++;
185                     if (turn > 3) turn = 0;
186                 }
187                 else
188                 {
189                     turn--;
190                     if (turn < 0) turn = 3;
191                 }
192             }
193             if (map[0][0] == y&&map[0][1] == x)
194             {
195                 printf("%d %s\n", i, ins[i]);
196                 break;
197             }
198             strcpy(ins[i], "Left");
199             map[0][0] = 0;
200             map[0][1] = 0;
201         }
202         
203     }
204     return 0;
205 }