深搜算法 6300：Grid Path Construction(2418)
6300：Grid Path Construction(2418)
时间限制: 1000 ms 内存限制: 524288 KB
提交数: 0 通过数: 0Special Judge
【题目描述】
Given an n×m grid and two squares a=(y1,x1) and b=(y2,x2), create a path from a to b that visits each square exactly once.
For example, here is a path from a=(1,3) to b=(3,6) in a 4×7 grid:
【输入】
The first input line has an integer t: the number of tests.
After this, there are t lines that describe the tests. Each line has six integers n, m, y1, x1, y2 and x2.
In all tests 1≤y1,y2≤n ja 1≤x1,x2≤m. In addition, y1≠y2 or x1≠x2.
【输出】
Print YES, if it is possible to construct a path, and NO otherwise.
If there is a path, also print its description which consists of characters U (up), D (down), L (left) ja R (right). If there are several paths, you can print any of them.
【输入样例】
5 1 3 1 1 1 3 1 3 1 2 1 3 2 2 1 1 2 2 2 2 1 1 2 1 4 7 1 3 3 6【输出样例】
YES RR NO NO YES RDL YES RRRRDDDLLLLLLUUURDDRURDRURD【提示】
1≤t≤100
1≤n≤50
1≤m≤50
#include <bits/stdc++.h> using namespace std; int g[51][51]; char str[3000]; void print(int &n,int &m); bool is(int &n,int &m,int x,int y,int &mx,int &my,int len){ if(x>=1 && x<=n && y>=1 && y<=m){ if(len<n*m-1){ if(x==mx && y==my)return false; else return true; } return true; } return false; } bool search(int &n,int &m,int x,int y,int &mx,int &my,int len){ //cout<<str<<endl; //printf("n=%d m=%d x=%d y=%d mx=%d my=%d len=%d\n",n,m,x,y,mx,my,len); //print(n,m); //x,y是当前位置 x是行 y是列 //mx,my是目标位置 //len是已寻找的路径长度 if(x==mx && y==my){ if(len==n*m-1){ str[len+1]='\0'; return true; } } int xx,yy; xx=x-1,yy=y; if(is(n,m,xx,yy,mx,my,len+1) && !g[xx][yy]){ str[len]='U'; g[xx][yy]=len+1;//随便标记 只要不是0就行 if(search(n,m,xx,yy,mx,my,len+1) )return true; else { g[xx][yy]=0; str[len]='\0'; } } xx=x,yy=y+1; if(is(n,m,xx,yy,mx,my,len+1) && !g[xx][yy]){ str[len]='R'; g[xx][yy]=len+1;//随便标记 只要不是0就行 if(search(n,m,xx,yy,mx,my,len+1) )return true; else { g[xx][yy]=0; str[len]='\0'; } } xx=x+1,yy=y; if(is(n,m,xx,yy,mx,my,len+1) && !g[xx][yy]){ str[len]='D'; g[xx][yy]=len+1;//随便标记 只要不是0就行 if(search(n,m,xx,yy,mx,my,len+1) )return true; else { g[xx][yy]=0; str[len]='\0'; } } xx=x,yy=y-1; if(is(n,m,xx,yy,mx,my,len+1) && !g[xx][yy]){ str[len]='L'; g[xx][yy]=len+1;//随便标记 只要不是0就行 if(search(n,m,xx,yy,mx,my,len+1) )return true; else { g[xx][yy]=0; str[len]='\0'; } } return false; } void print(int &n,int &m){ printf("路径展示:99是起点\n"); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) printf("%2d ",g[i][j]); printf("\n"); } printf("\n"); } int main(int argc, char** argv) { int t,n,m,x1,y1,x2,y2; cin>>t; for(int i=0;i<t;i++) { cin>>n>>m>>x1>>y1>>x2>>y2; memset(g,0,sizeof(g)); memset(str,'\0',sizeof(str)); g[x1][y1]=99; if(search(n,m,x1,y1,x2,y2,0)) { cout<<"YES\n"<<str<<endl; print(n,m); } else cout<<"NO"<<endl; } return 0; }