QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18329 | #2265. Short Coding | Wu_Ren# | WA | 5ms | 3832kb | C++11 | 1.6kb | 2022-01-17 21:07:52 | 2022-05-04 17:58:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,K;
int sx,sy,tx,ty,re[5]={0,7,1,9,2},a[5],ans=5,fx[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char s[20][20];
string nm[]={"","LEFT","RIGHT","FORWARD","IF-OPEN","GOTO"};
struct op{
int ty,w;
}md[13]={{1,0},{2,0},{3,0},{4,0},{4,1},{4,2},{4,3},{4,4},{5,0},{5,1},{5,2},{5,3},{5,4}};
struct sta{
int x,y,dir,p;
bool operator <(const sta &b)const{
return x*10000+y*100+dir*10+p<b.x*10000+b.y*100+b.dir*10+b.p;
}
};
map<sta,bool>vis;
bool chk(int k){
vis.clear();
sta nw={sx,sy,0,0};
while(nw.x!=tx||nw.y!=ty){
if(vis[nw]) return 0;
vis[nw]=1;
op x=md[a[nw.p]];
if(x.ty==1){
nw.dir=(nw.dir+1)&3;
nw.p=(nw.p+1)%k;
}
if(x.ty==2){
nw.dir=(nw.dir+3)&3;
nw.p=(nw.p+1)%k;
}
if(x.ty==3){
int xx=nw.x+fx[nw.dir][0],yy=nw.y+fx[nw.dir][1];
if(1<=xx&&xx<=n&&1<=yy&&yy<=m&&s[xx][yy]!='#') nw.x=xx,nw.y=yy;
nw.p=(nw.p+1)%k;
}
if(x.ty==4) nw.p=x.w;
if(x.ty==5){
int xx=nw.x+fx[nw.dir][0],yy=nw.y+fx[nw.dir][1];
if(1<=xx&&xx<=n&&1<=yy&&yy<=m&&s[xx][yy]!='#') nw.p=x.w;
else nw.p=(nw.p+1)%k;
}
}
return 1;
}
void dfs(int d){
if(d>=ans) return;
if(d&&chk(d)){
ans=d;
for(int i=0;i<d;i++) re[i]=a[i];
}
for(int i=0;i<13;i++) a[d]=i,dfs(d+1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int j=1;j<=m;j++){
if(s[i][j]=='S') sx=i,sy=j;
if(s[i][j]=='G') tx=i,ty=j;
}
}
dfs(0);
printf("%d\n",ans);
for(int i=0;i<ans;i++){
cout<<nm[md[re[i]].ty];
if(md[re[i]].ty>=4) printf(" %d\n",md[re[i]].w+1);
else puts("");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3744kb
input:
4 2 S# .# .# G.
output:
1 FORWARD
result:
ok correct answer!
Test #2:
score: 0
Accepted
time: 3ms
memory: 3832kb
input:
3 6 ##S..# #..##. .G..#.
output:
2 FORWARD RIGHT
result:
ok correct answer!
Test #3:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
3 7 ....S## .#.#... ##.#.G#
output:
2 FORWARD LEFT
result:
ok correct answer!
Test #4:
score: 0
Accepted
time: 5ms
memory: 3812kb
input:
4 8 ...S.#.# ##..#.#. ###...#. #.#.#G.#
output:
3 FORWARD FORWARD LEFT
result:
ok correct answer!
Test #5:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
3 5 .S#.. ..... ..#G.
output:
3 FORWARD LEFT FORWARD
result:
ok correct answer!
Test #6:
score: -100
Wrong Answer
time: 3ms
memory: 3828kb
input:
10 10 .....S#... ...#...... ....##.... .#.....#.. ....#..... ..#....... ...#...... .......... .#...#.... G.#..#...#
output:
3 LEFT FORWARD GOTO 2
result:
wrong answer your program is not correct.