Nguồn đề bài: UVA118
1. Dịch đề UVA118 sang Tiếng Việt
UVA118. THĂM DÒ THẾ GIỚI PHẲNG
Khoa học người máy, nghiên cứu về chuyển động của robot và học máy là những lĩnh vực đã vượt khỏi ranh giới của nhiều ngành trong Khoa học máy tính: Trí tuệ nhân tạo, Thuật toán và độ phức tạp, Kỹ thuật điện và cơ khí. Hơn nữa, những con robot cũng như “những chú rùa” (lấy cảm hứng từ công trình của Papert, Abelson và diSessa) hay giống “beeper-pickers” (lấy cảm hứng từ công trình của Pattis) đã được các sinh viên nghiên cứu và sử dụng trong khóa học về nhập môn lập trình trong nhiều năm. Bài toán này có liên quan đến việc xác định vị trí của một robot đang thám hiểm thế giới phẳng thời tiền Columbus. Cho trước một lưới chữ nhật và một dãy các vị trí của robot cùng những chỉ dẫn, hãy viết một chương trình xác định từng dẫy vị trí robot và chỉ dẫn đến vị trí cuối cùng của robot. Vị trí của một robot bao gồm toạ độ lưới (một cặp số nguyên: toạ độ x và y) và hướng (N, S, E, W chỉ các hướng Bắc, Nam, Đông và Tây). Một chỉ dẫn robot là một chuỗi ký tự ‘L’, ‘R’, và ‘F’ tương ứng như sau:
Left: robot quay trái 90 độ và giữ nguyên vị trí tại điểm lưới hiện tại.
Right: robot quay phải 90 độ và giữ nguyên vị trí tại điểm lưới hiện tại.
Forward: robot tiến lên một điểm lưới theo phương hướng hiện tại và giữ nguyên hướng.
Phương Bắc tương ứng với phương từ điểm lưới (x,y) đến điểm lưới (x, y+1) Vì lưới hình chữ nhật và có đường biên, một robot di chuyển ra ngoài rìa của lưới bị coi như mất tích vĩnh viễn. Tuy nhiên, những robot đã mất tích sẽ lưu lại một “mùi” ngăn cản những robot khác lặp lại sai lầm tương tự (nghĩa là bị rơi ra khỏi lưới ở vị trí mà trước đây đã có con bị rơi). Mùi này sẽ lưu lại ở vị trí lưới cuối cùng mà con robot trước đó đã đứng trước khi tiến thêm một bước nữa và lọt ra ngoài lưới. Chỉ dẫn để một con robot bị lọt ra ngoài lưới sẽ bị những con robot sau loại bỏ không nghe nữa.
INPUT
Dòng đầu là toạ độ góc trên bên phải của lưới chữ nhật, toạ độ góc dưới bên trái được giả định đặt ở điểm (0,0).
Còn lại sẽ là dãy các vị trí của robot và các chỉ dẫn (mỗi robot 2 dòng). Vị trí gồm 2 số nguyên cho biết toạ độ xuất phát của robot và hướng (N, S, E, W), tất cả được viết trên cùng một dòng và phân tách nhau bởi dấu cách. Chỉ dẫn robot là một chuỗi các ký tự ‘L’, ‘R’, và ‘F’ được viết trên cùng một dòng. Mỗi robot được xử lý tuần tự, tức là sau khi thực hiện toàn bộ chỉ dẫn của robot này xong mới đến robot khác. File input kết thúc ký tự EOF. Có thể giả thiết rằng tất cả các vị trí khởi đầu của robot đều nằm trong vùng biên của lưới đã cho. Giá trị lớn nhất của bất kỳ một toạ độ nào là 50. Tất cả các chuỗi chỉ dẫn đều có độ dài ít hơn 100 ký tự.
OUTPUT
Với mỗi vị trí/chỉ dẫn của một robot trong file input, output sẽ chỉ ra vị trí lưới cuối cùng và hướng của robot đó. Nếu một robot rơi khỏi cạnh lưới thì máy tính in ra từ “LOST” phía sau vị trí và hướng của nó.
2. Code tham khảo (solution pascal + c++)
#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
using namespace std;
int main()
{
int x,y,a,b,a1,b1,i;
string s;
char c;
bool d;
map<pair<int,int>,int>nt;
cin>>x>>y;
while(cin>>a>>b>>c>>s)
{
d=true;
for(i=0;i<s.length();i++)
{
if(s[i]=='L'){
if(c=='N')c='W';
else if(c=='W')c='S';
else if(c=='S')c='E';
else if(c=='E')c='N';
}
else if(s[i]=='R'){
if(c=='N')c='E';
else if(c=='E')c='S';
else if(c=='S')c='W';
else if(c=='W')c='N';
}
else if(s[i]=='F'){
if(c=='N'){
b1=b+1;
if(b1>y){
if(nt[make_pair(a,b)]!=1){
nt[make_pair(a,b)]=1;
d=false;
break;
}
}
else b++;
}
else if(c=='E'){
a1=a+1;
if(a1>x){
if(nt[make_pair(a,b)]!=1){
nt[make_pair(a,b)]=1;
d=false;
break;
}
}
else a++;
}
else if(c=='S'){
b1=b-1;
if(b1<0){
if(nt[make_pair(a,b)]!=1){
nt[make_pair(a,b)]=1;
d=false;
break;
}
}
else b--;
}
else if(c=='W'){
a1=a-1;
if(a1<0){
if(nt[make_pair(a,b)]!=1){
nt[make_pair(a,b)]=1;
d=false;
break;
}
}
else a--;
}
}
if(d==false)break;
}
cout<<a<<" "<<b<<" "<<c;
if(d==false) cout<<" LOST";
cout<<endl;
}
return 0;
}Code pascal dưới đây là của mình viết. nhưng nó đã sai, mình ko biết sai chỗ nào nữa. nhưng thôi cứ up lên cho các bạn tham khảo. nếu tìm được lỗi sai trong code dưới đây vui lòng cmt phía dưới nhé. cảm ơn
const fi='';
nmax=5000;
type data=longint;
var
f:text;
S:string;
maxx,maxy,x,y:data;
c:char;
dd:array[-nmax..nmax+1,-nmax..nmax+1] of boolean;
d:boolean;
procedure xuli;
var i,j:data;
begin
d:=true;
for i:=1 to length(s) do
begin
if s[i]='F' then
begin
case c of
'N':
if y+1>maxy then
begin
if not dd[x,y+1] then
begin
dd[x,y+1]:=true;
d:=false;
break;
end;
end
else
inc(y);
'E':
if x+1>maxx then
begin
if not dd[x+1,y] then
begin
dd[x+1,y]:=true;
d:=false;
break;
end;
end
else
inc(x);
'S':
if y-1<0 then
begin
if not dd[x,y-1] then
begin
dd[x,y-1]:=true;
d:=false;
break;
end;
end
else
dec(y);
'W':
if x-1<0 then
begin
if not dd[x-1,y] then
begin
dd[x-1,y]:=true;
d:=false;
break;
end;
end
else
dec(x);
end;
continue;
end;
case S[i] of
'L':
begin
case c of
'N': c:='W';
'W': c:='S';
'S': c:='E';
'E': c:='N';
end;
end;
'R':
begin
case c of
'N': c:='E';
'E': c:='S';
'S': c:='W';
'W': c:='N';
end;
end;
end;
end;
write(x,' ',y,' ',c);
if d=false then
writeln(' LOST')
else
writeln;
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,maxx,maxy);
while not eof(f) do
begin
read(f,x,y); read(f,c); readln(f,c);
readln(f,s);
xuli;
end;
close(f);
end;
begin
docfile;
readln;
end.
uva muon nam