深搜算法 6300：Grid Path Construction(2418)

6300Grid 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≤1001≤n≤501≤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(x1 xn y1 ym){ if(lenn*m-1){ if(xmx ymy)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){ //coutstrendl; //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(xmx ymy){ if(lenn*m-1){ str[len1]\0; return true; } } int xx,yy; xxx-1,yyy; if(is(n,m,xx,yy,mx,my,len1) !g[xx][yy]){ str[len]U; g[xx][yy]len1;//随便标记 只要不是0就行 if(search(n,m,xx,yy,mx,my,len1) )return true; else { g[xx][yy]0; str[len]\0; } } xxx,yyy1; if(is(n,m,xx,yy,mx,my,len1) !g[xx][yy]){ str[len]R; g[xx][yy]len1;//随便标记 只要不是0就行 if(search(n,m,xx,yy,mx,my,len1) )return true; else { g[xx][yy]0; str[len]\0; } } xxx1,yyy; if(is(n,m,xx,yy,mx,my,len1) !g[xx][yy]){ str[len]D; g[xx][yy]len1;//随便标记 只要不是0就行 if(search(n,m,xx,yy,mx,my,len1) )return true; else { g[xx][yy]0; str[len]\0; } } xxx,yyy-1; if(is(n,m,xx,yy,mx,my,len1) !g[xx][yy]){ str[len]L; g[xx][yy]len1;//随便标记 只要不是0就行 if(search(n,m,xx,yy,mx,my,len1) )return true; else { g[xx][yy]0; str[len]\0; } } return false; } void print(int n,int m){ printf(路径展示:99是起点\n); for(int i1;in;i){ for(int j1;jm;j) printf(%2d ,g[i][j]); printf(\n); } printf(\n); } int main(int argc, char** argv) { int t,n,m,x1,y1,x2,y2; cint; for(int i0;it;i) { cinnmx1y1x2y2; memset(g,0,sizeof(g)); memset(str,\0,sizeof(str)); g[x1][y1]99; if(search(n,m,x1,y1,x2,y2,0)) { coutYES\nstrendl; print(n,m); } else coutNOendl; } return 0; }