POJ 2632-rashing Robots
50936 ワード
転載は出典を明記してください.優YoU http://user.qzone.qq.com/289065406/blog/1299147655
ヒント:簡単なシミュレーションです.プログラムが長いのはアルゴリズムのせいではなく、多くの場合を考慮しなければならないので、忍耐力が必要です.
注意が必要なのは、座標系が変換されると、方向の変化に注意することです.
注意事項:
1、座標系を二次元マトリックスの形に変えたいです.N、W、S、Eの方向変化に注意しなければなりません.座標系を変えた後、Nは南、Sは北、WEは変わらず、Lは右、Rは左、Fは変わらないです.
2、剰余を求める処理に対してマイナスの状況に注意するかどうか.
3、robot移動中に、crases robotとcrases wallは同時に判断して、crases robotは前に置く.
追加試験データ:
Sample Input
8
5 4
2
1 E
5 4 W
1 F 7
2 F 7
5 4
2 4
1 E
5 4 W
1 F 3
2 F 1
1 L 1
1 F 3
5 4
2
1 E
5 4 W
1 L 96
1 F 2
5 4
2 3
1 E
5 4 W
1 F 4
1 L 1
1 F 20
9 5
5 19
2 4 E
4 3 N
6 2 E
9 5 S
9 1 W
4 F 1
4 R 1
4 F 6
4 L 5
4 F 3
4 L 1
5 R 1
5 F 3
5 L 1
5 F 2
5 L 1
5 F 3
5 R 5
5 F 2
5 R 1
5 F 2
4 F 2
4 L 1
4 F 3
9 5
2 6
9 5 S
9 1 W
1 F 1
1 R 1
1 F 2
2 F 2
2 R 1
2 F 3
5 4
2
1 E
5 4 W
1 R 1
1 F 2
5 4
2
1 E
5 4 W
1 L 1
1 F 2
Sample Output
Robot 1 crassis into the wall
Robot 1 crassis into robot 2
OK
Robot 1 crassis into robot 2
Robot 4 crassis into robot 5
Robot 2 crassis into robot 1
Robot 1 crassis into the wall
OK
1 //Memory Time
2 //348K 16MS
3
4 #include<iostream>
5 using namespace std;
6
7 int main(void)
8 {
9 int cases;
10 int a,b; //A B
11 int n,m; //n : robot , m :
12 int x,y; //robots
13 char dire; //robots
14 int rob[101],rep[101]; //rob: ,rep:
15 char act[101]; //act:
16
17 bool flag=false;
18 int i,k;
19
20 int post[101][101]; // robot
21 int num[101][101]; // robot
22 int xx[101],yy[101]; // robot
23
24 cin>>cases;
25 while(cases--)
26 {
27 memset(post,-1,sizeof(post));
28 memset(num,0,sizeof(num));
29 memset(xx,0,sizeof(xx));
30 memset(yy,0,sizeof(yy));
31
32 cin>>a>>b;
33 cin>>n>>m;
34
35 /*Input the postion and direction of each robot*/
36 for(i=1;i<=n;i++)
37 {
38 cin>>y>>x>>dire; // cin ， char
39 xx[i]=x;
40 yy[i]=y; // （ ， ）
41 num[x][y]=i; // （ ， ）
42 if(dire=='S') // （ ， ）
43 post[x][y]=0; //0 or 360 【 ， ， N ，S ， WE 】
44 else if(dire=='E')
45 post[x][y]=1; //90
46 else if(dire=='N')
47 post[x][y]=2; //180
48 else if(dire=='W')
49 post[x][y]=3; //270
50 } // 0~3
51
52 /*Input < robot #> < action> < repeat>*/
53 for(k=1;k<=m;k++)
54 cin>>rob[k]>>act[k]>>rep[k];
55
56 bool flag=false;
57 int row,col;
58 for(k=1;k<=m;k++)
59 {
60 row=xx[rob[k]];
61 col=yy[rob[k]];
62
63 if(act[k]=='L') //【 ， ：L ，R 】
64 {
65 rep[k]%=4; // 4 （360 ）
66 post[row][col] = ( post[row][col] + rep[k] ) % 4;
67 }
68 else if(act[k]=='R')
69 {
70 rep[k]%=4;
71 post[row][col] = ( post[row][col] - rep[k] ) % 4;
72 if(post[row][col]<0) //
73 post[row][col]+=4;
74 }
75 else if(act[k]=='F')
76 {
77 if(post[row][col]==0) //N
78 for(i=1;i<=rep[k];i++)
79 {
80 if(num[row-i][col]) // （ robot）
81 {
82 cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row-i][col]<<endl;
83 flag=true;
84 break;
85 }
86 if(row-i<1) //
87 {
88 cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;
89 flag=true;
90 break;
91 }
92 if(i==rep[k])
93 { // ， robot
94 post[row][col]=-1; //
95 num[row][col]=0; //
96 row-=rep[k];
97 xx[rob[k]]-=rep[k];
98 post[row][col]=0; //
99 num[row][col]=rob[k]; //
100 }
101 }
102 else if(post[row][col]==1) //E
103 for(i=1;i<=rep[k];i++)
104 {
105 if(num[row][col+i])
106 {
107 cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row][col+i]<<endl;
108 flag=true;
109 break;
110 }
111 if(col+i>a)
112 {
113 cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;
114 flag=true;
115 break;
116 }
117 if(i==rep[k])
118 {
119 post[row][col]=-1;
120 num[row][col]=0;
121 col+=rep[k];
122 yy[rob[k]]+=rep[k];
123 post[row][col]=1;
124 num[row][col]=rob[k];
125 }
126 }
127 else if(post[row][col]==2) //S
128 for(i=1;i<=rep[k];i++)
129 {
130 if(num[row+i][col])
131 {
132 cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row+i][col]<<endl;
133 flag=true;
134 break;
135 }
136 if(row+i>b)
137 {
138 cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;
139 flag=true;
140 break;
141 }
142 if(i==rep[k])
143 {
144 post[row][col]=-1;
145 num[row][col]=0;
146 row+=rep[k];
147 xx[rob[k]]+=rep[k];
148 post[row][col]=2;
149 num[row][col]=rob[k];
150 }
151 }
152 else if(post[row][col]==3) //W
153 for(i=1;i<=rep[k];i++)
154 {
155 if(num[row][col-i])
156 {
157 cout<<"Robot "<<num[row][col]<<" crashes into robot "<<num[row][col-i]<<endl;
158 flag=true;
159 break;
160 }
161 if(col-i<1)
162 {
163 cout<<"Robot "<<num[row][col]<<" crashes into the wall"<<endl;
164 flag=true;
165 break;
166 }
167 if(i==rep[k])
168 {
169 post[row][col]=-1;
170 num[row][col]=0;
171 col-=rep[k];
172 yy[rob[k]]-=rep[k];
173 post[row][col]=3;
174 num[row][col]=rob[k];
175 }
176 }
177 }
178 if(flag)break;
179 }
180 if(!flag)
181 cout<<"OK"<<endl;
182 }
183 return 0;
184 }