May any one help me in my wrong?
this code got WA.
I used bfs one board by cosidering 4 different ways to enter each block.
this is my code.
please help me.
thanks.
Code: Select all
#include<iostream>
#include<fstream>
#include<algorithm>
#include<stdio.h>
#include<strstream>
using namespace std;
char blocks[100000][4];
char paths[100000][4];
bool gone[100000][4][4];
struct pos{
int c,r,dir;
};
pos path[1000000];
int n;
int valid(pos p) {
if(p.r<0||p.r>=4||p.c<0)
return 0;
if(p.c>=n)
return 2;
if(gone[p.r][p.c][p.dir]||blocks[p.r][p.c]=='X')
return 0;
gone[p.r][p.c][p.dir]=true;
return 1;
}
bool bfs() {
int i,j,k,cnt=0;
pos nex;
for(j=0;j<n;j++)
for(i=0;i<4;i++)
for(k=0;k<4;k++)
gone[i][j][k]=false;
for(i=0;i<4;i++) {
if(blocks[i][0]=='A') {
path[cnt].c=0;
path[cnt].r=i;
path[cnt++].dir=0;
gone[i][0][0]=gone[i][0][1]=true;
}
if(blocks[i][0]=='B') {
path[cnt].c=0;
path[cnt].r=i;
path[cnt++].dir=0;
gone[i][0][0]=true;
}
}
pos cur;
for(i=0;i<cnt;i++) {
cur=path[i];
if(blocks[cur.r][cur.c]=='A') {
if(cur.dir==0) {
nex=cur;
nex.c++;
if(k=valid(nex)) {
if(k==2)
return true;
path[cnt++]=nex;
}
}
else if(cur.dir==1) {
nex=cur;
nex.c--;
if(k=valid(nex)) {
path[cnt++]=nex;
}
}
else if(cur.dir==2) {
nex=cur;
nex.r++;
if(k=valid(nex)) {
path[cnt++]=nex;
}
}
else if(cur.dir==3) {
nex=cur;
nex.r--;
if(k=valid(nex)) {
path[cnt++]=nex;
}
}
}
if(blocks[cur.r][cur.c]=='B') {
if(cur.dir==0||cur.dir==1) {
nex=cur;
nex.r--;
nex.dir=3;
if(k=valid(nex)) {
path[cnt++]=nex;
}
nex=cur;
nex.r++;
nex.dir=2;
if(k=valid(nex)) {
path[cnt++]=nex;
}
}
else if(cur.dir==2||cur.dir==3) {
nex=cur;
nex.c--;
nex.dir=1;
if(k=valid(nex)) {
path[cnt++]=nex;
}
nex=cur;
nex.c++;
nex.dir=0;
if(k=valid(nex)) {
if(k==2)
return true;
path[cnt++]=nex;
}
}
}
}
return false;
}
int main() {
//ifstream cin("input.txt");
int i,j,k,t;
cin>>t;
while(t--) {
cin>>n;
for(j=0;j<4;j++) {
//for(i=0;i<n;i++) {
cin>>blocks[j];
//}
}
if(bfs())
cout<<"Try."<<endl;
else
cout<<"Don't Try."<<endl;
}
}
