|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include <iostream> #include <cstdio> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> using namespace std; bool gr[30][30][7][7]; //bool gr2D[30][30]; struct Point{ int x,y,velocity,accleration; int val; }; Point St,Fn; int m,n; void bfs() { int x,y,v,a,val; int dx,dy,tx,ty; queue<int> q; q.push(St.x);q.push(St.y); q.push(0);q.push(0);q.push(0); gr[St.x][St.y][0+3][0+3]=1; while(!q.empty()) { x=q.front();q.pop(); y=q.front();q.pop(); v=q.front();q.pop(); a=q.front();q.pop(); val = q.front();q.pop(); //cout<<x<<" "<<y<<" "<<v<<" "<<a<<" "<<val<<"\n"; if(x==Fn.x && y ==Fn.y) { printf("Optimal solution takes %d hops.\n", val); return; } for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++) { tx = v+i; ty = a+j; if(abs(tx)<=3 && abs(ty)<=3) { dx = x+v+i; dy = y+a+j; if(dx>=0 && dx<m && dy>=0 && dy<n && gr[dx][dy][tx+3][ty+3]==0) { //if(gr2D[dx][dy]) //continue; gr[dx][dy][tx+3][ty+3]=1; q.push(dx); q.push(dy); q.push(tx); q.push(ty); q.push(val+1); } } } } printf("No solution.\n"); } int main() { int t,p; scanf("%d",&t); int x1,x2,y1,y2; Point A,B; while(t--) { scanf("%d%d",&m,&n); memset(gr,0,sizeof(gr)); //memset(gr,0,sizeof(gr2D)); scanf("%d%d%d%d",&St.x,&St.y,&Fn.x,&Fn.y); scanf("%d",&p); bool flag=1; while(p--) { scanf("%d%d%d%d",&x1,&x2,&y1,&y2); for(int i=x1;i<=x2;i++) { for(int j=y1;j<=y2;j++) { //gr2D[i][j]=1; for(int k=0;k<7;k++) { for(int l=0;l<7;l++) { gr[i][j][k][l]=1; if(i==Fn.x && j==Fn.y) flag=0; } } } } } if(St.x==Fn.x && St.y==Fn.y) printf("Optimal solution takes 0 hops.\n"); else { if(flag==0) printf("No solution.\n"); else bfs(); } } return 0; } |