Moderator: Board moderators
Code: Select all
3 3 N LOST //so 3 3 coordinate is block
Code: Select all
LLFFFLFLFL
start 0 3 W
L -> 0 3 S [change dir to left]
L -> 0 3 E
F -> 1 3 E
F -> 2 3 E
[b]#F -> 3 3 E [this step is not valid becoz 3 3 already visited by 2nd robot] [so this step remain 2 3 E][/b]
L -> 2 3 N
F -> 2 4 N [this time it is lost becoz right boundary is x=5 y=3]
SO result should be [b]2 3 N[/b]
How it is [b]2 3 S[/b]
Code: Select all
0 3 W
0 3 S
0 3 E
1 3 E
2 3 E
3 3 E
3 3 N
3 3 N
3 3 W
2 3 W
2 3 S
You can surely go with a cell with "scent" but you can not "fell off" the world from that cell.An instruction to move ``off'' the world from a grid point from which a robot has been previously lost is simply ignored by the current robot.
Code: Select all
3 3
0 0 W
F
0 0 S
FCode: Select all
0 0 W LOST
0 0 SI got WA....help me please.
Code: Select all
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <climits>
#include <iostream>
#include<iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <sstream>
#include <algorithm>
using namespace std;
#define MAX 10000007
#define PI acos(-1.0)
#define int64 long long
#define pb push_back
#define sf scanf
#define pf printf
#define READ(f) freopen(f, "r", stdin)
#define mem(a,b) memset(a,b,sizeof(a))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1}; //4 Direction: east, north, west, south
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
inline int get_index(char dir)
{
if(dir == 'E') return 0;
if(dir == 'N') return 1;
if(dir == 'W') return 2;
if(dir == 'S') return 3;
}
inline char get_dir(int index)
{
if(index == 0) return 'E';
if(index == 1) return 'N';
if(index == 2) return 'W';
if(index == 3) return 'S';
}
int main()
{
READ("118 - Mutant Flatworld Explorers.in");
int fx, fy;
char dir;
int rx, ry;
string input;
map<pair<int, int>, int>m;
sf("%d %d",&fx, &fy);
while(sf("%d %d %c\n",&rx, &ry, &dir) != EOF)
{
getline(cin,input);
int l = input.length();
int index = get_index(dir);
bool flag = false;
for(int i = 0; i < l; i++)
{
if(input[i] == 'R') index = (index + 3) % 4;
else if(input[i] == 'L') index = (index + 5) % 4;
else if(input[i] == 'F')
{
rx += dx[index];
ry += dy[index];
if(rx < 0 || rx > fx || ry < 0 || ry > fy)
{
rx -= dx[index];
ry -= dy[index];
pair<int, int>pii;
pii = make_pair(rx, ry);
if(m.find(pii) == m.end()) m[pii] = 0;
else continue;
flag = true;
break;
}
}
}
dir = get_dir(index);
pf("%d %d %c",rx, ry, dir);
if(flag) pf(" LOST\n");
else pf("\n");
}
return 0;
}
Yes, I found the problem and got AC.
Code: Select all
#include <iostream>
#include <vector>
#include <algorithm>
// #include <utility>
#include <string>
// #include <stack>
using namespace std;
vector<vector<int> > a(51,vector<int>(51));
int lasti=0,lastj=0,lastdir=0;
int y,x;
string ins;
char dirmap(int dir){
if(dir==0)return 'N';
if(dir==1)return 'E';
if(dir==2)return 'S';
return 'W';
}
int dirm(char dir){
switch(dir){
case 'N': return 0;
case 'E': return 1;
case 'S': return 2;
default: return 3;
}
}
int move(int i,int j,int dir,int k){
// cout<<i<<' '<<j<<' '<<dir<<endl;
if(i>x||j>y||i<0||j<0){
if(a[lasti][lastj]==1)return move(lasti,lastj,dir,k);
else return 1;
}
lasti=i,lastj=j;lastdir=dir;
if(k==ins.size())return 0;
if(ins[k]=='L')return move(i,j,(dir-1+4)%4,k+1);
else if(ins[k]=='R')return move(i,j,(dir+1)%4,k+1);
else {
switch(dir){
case 0: return move(i-1,j,dir,k+1);
case 1: return move(i,j+1,dir,k+1);
case 2: return move(i+1,j,dir,k+1);
default: return move(i,j-1,dir,k+1);
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin>>y>>x;
while(!cin.eof()){
int c,r;
char dir;
cin>>c>>r>>dir;
r=x-r;
ws(cin);
getline(cin,ins);
int numdir=dirm(dir);
int lost=move(r,c,numdir,0);
if(lost){
a[lasti][lastj]=1;
cout<<lastj<<' '<<x-lasti<<' '<<dirmap(lastdir)<<" LOST"<<endl;
}
else cout<<lastj<<' '<<x-lasti<<' '<<dirmap(lastdir)<<endl;
}
}