QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#18032 | #2265. Short Coding | _silhouette_# | WA | 4ms | 3868kb | C++ | 2.2kb | 2022-01-15 19:39:53 | 2022-05-04 16:43:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,Ans[10],A[10],vis[20][20][10][5];
char a[15][15];
void Print(int x){
if(x==1) puts("LEFT");
if(x==2) puts("RIGHT");
if(x==3) puts("FORWARD");
if(x==4) puts("IF-OPEN 1");
if(x==5) puts("IF-OPEN 2");
if(x==6) puts("IF-OPEN 3");
if(x==7) puts("IF-OPEN 4");
if(x==8) puts("GOTO 1");
if(x==9) puts("GOTO 2");
if(x==10) puts("GOTO 3");
if(x==11) puts("GOTO 4");
}
bool dfs(int x,int y,int op,int f,int tot){//DLUR
if(op>tot) return dfs(x,y,op-tot,f,tot);
if(vis[x][y][op][f]) return false;
if(a[x][y]=='G') return true;
vis[x][y][op][f]=1;
if(A[op]==1) return dfs(x,y,op+1,(f+3)%4,tot);
if(A[op]==2) return dfs(x,y,op+1,(f+1)%4,tot);
if(A[op]==3){
if(f==0)
if(x+1<=n&&a[x+1][y]!='#') return dfs(x+1,y,op+1,f,tot);
if(f==1)
if(y-1>=1&&a[x][y-1]!='#') return dfs(x,y-1,op+1,f,tot);
if(f==2)
if(x-1>=1&&a[x-1][y]!='#') return dfs(x-1,y,op+1,f,tot);
if(f==3)
if(y+1<=m&&a[x][y+1]!='#') return dfs(x,y+1,op+1,f,tot);
return dfs(x,y,op+1,f,tot);
}
if(A[op]>=4&&A[op]<=7){
if(f==0)
if(x+1<=n&&a[x+1][y]!='#') return dfs(x,y,A[op]-3,f,tot);
if(f==1)
if(y-1>=1&&a[x][y-1]!='#') return dfs(x,y,A[op]-3,f,tot);
if(f==2)
if(x-1>=1&&a[x-1][y]!='#') return dfs(x,y,A[op]-3,f,tot);
if(f==3)
if(y+1<=m&&a[x][y+1]!='#') return dfs(x,y,A[op]-3,f,tot);
return dfs(x,y,op+1,f,tot);
}
return dfs(x,y,A[op]-7,f,tot);
}
bool chck(int tot){
if(tot==0) return false;
for(int i=1;i<=tot;i++)
if(4<=A[i]&&A[i]<=7&&A[i]-3>tot) return false;
int sx=1,sy=0;
for(int i=1;i<=m;i++)
if(a[1][i]=='S') sy=i;
memset(vis,0,sizeof(vis));
return dfs(sx,sy,1,0,tot);
}
void dfs(int x){
if(x-1>=ans) return;
if(chck(x-1)){
ans=x-1;
for(int i=1;i<=ans;i++) Ans[i]=A[i];
}
for(int i=1;i<=11;i++)
if(!(4<=i&&i<=7&&i-3<=x)&&!(i>7&&i-7>=x))
A[x]=i,dfs(x+1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
ans=5; dfs(1);
if(ans==5){
puts("5");
puts("RIGHT");
puts("IF-OPEN 5");
puts("LEFT");
puts("GOTO 2");
puts("FORWARD");
} else {
printf("%d\n",ans);
for(int i=1;i<=ans;i++) Print(Ans[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3852kb
input:
4 2 S# .# .# G.
output:
1 FORWARD
result:
ok correct answer!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
3 6 ##S..# #..##. .G..#.
output:
2 FORWARD RIGHT
result:
ok correct answer!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
3 7 ....S## .#.#... ##.#.G#
output:
2 FORWARD LEFT
result:
ok correct answer!
Test #4:
score: 0
Accepted
time: 4ms
memory: 3868kb
input:
4 8 ...S.#.# ##..#.#. ###...#. #.#.#G.#
output:
3 FORWARD FORWARD LEFT
result:
ok correct answer!
Test #5:
score: 0
Accepted
time: 3ms
memory: 3836kb
input:
3 5 .S#.. ..... ..#G.
output:
3 FORWARD LEFT FORWARD
result:
ok correct answer!
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3784kb
input:
10 10 .....S#... ...#...... ....##.... .#.....#.. ....#..... ..#....... ...#...... .......... .#...#.... G.#..#...#
output:
4 LEFT FORWARD FORWARD FORWARD
result:
wrong answer wrong answer. the length of your program is 3 but the optimal one is 4.