My output has the same number of moves as your output. Could you please check what's wrong with my code :
Code: Select all
#include <iostream>
#define MAXK 1005
#define MAXP 15
#define MAXQ 15
using namespace std;
int m,n,k,p,q,x0,y0,k0;
bool c[MAXK][MAXK];
int pq[MAXK*(MAXP+1)*(2*MAXQ+1)*3];
int d[MAXK],a[MAXK];
int pre[MAXK][2*MAXQ+1][MAXP+1];
int path[4*MAXK];
int head,tail;
void add(int u, int w, int x, int y){
if (d[u]>=0 || a[u]) return;
d[u]=w;pq[tail++]=u;
if (w==(abs(x-x0)+abs(y-y0))) c[k0][u]=1;
}
void bfs(int u){
for (int i=0;i<k;i++) d[i]=-1;
int x,y,w;
d[u]=0;
head=0,tail=1;pq[0]=u;
while (head<tail){
u=pq[head++];w=d[u]+1;
x=u/m,y=u%m;
if (x>0) add(u-m,w,x-1,y);
if (x<n-1) add(u+m,w,x+1,y);
if (y>0) add(u-1,w,x,y-1);
if (y<m-1) add(u+1,w,x,y+1);
}
}
void backtrack(int v, int nx, int ny){
int k=0,next,dx,dy;
while (1){
path[k++]=v;
if (v==0) break;
next=pre[v][nx+MAXQ][ny];
v-=nx*m+ny;
dx=(next/10)-1,dy=(next%10)-1;
nx-=dx,ny-=dy;
}
cout<<k-1<<endl;
for (int i=k-1;i>=0;i--){
v=path[i];
cout<<(v%m)+1<<' '<<(v/m)+1<<endl;
}
}
void find(int u, int vx, int vy){
for (int i=0;i<k;i++)
for (int dx=-q;dx<=q;dx++)
for (int dy=0;dy<=p;dy++)
pre[i][dx+MAXQ][dy]=-1;
head=0,tail=3;
pq[0]=u,pq[1]=vx,pq[2]=vy;
pre[u][vx+MAXQ][vy]=0;
int v,nx,ny,x,y,xx,yy;
bool f;
while (head<tail){
u=pq[head++];vx=pq[head++];vy=pq[head++];
x=u/m,y=u%m;
for (int dy=1;dy>=-1;dy--)
for (int dx=1;dx>=-1;dx--){
nx=vx+dx,ny=vy+dy;
if (ny<0 || ny>p || nx<-q || nx>q || (ny==0 && nx<=0)) continue;
xx=x+nx,yy=y+ny;v=xx*m+yy;
if (xx<0 || xx>=n || yy<0 || yy>=m || a[v]) continue;
if (!c[u][v] || pre[v][nx+MAXQ][ny]>=0) continue;
pre[v][nx+MAXQ][ny]=(dx+1)*10+dy+1;
if (xx==n-1 && yy==m-1){
backtrack(v,nx,ny);
return;
}
pq[tail++]=v;pq[tail++]=nx;pq[tail++]=ny;
}
}
cout<<"Impossible"<<endl;
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
cin>>t;
while (t--){
cin>>m>>n>>p>>q;
k=n*m;
for (int i=0;i<k;i++) cin>>a[i];
for (int i=0;i<k;i++)
for (int j=0;j<k;j++)
c[i][j]=0;
for (int i=0;i<k;i++)
if (a[i]==0){
x0=i/m,y0=i%m,k0=i;
bfs(i);
}
find(0,0,0);
if (t) cout<<endl;
}
}