链接:https://ac.nowcoder.com/acm/contest/330/B
来源:牛客网
题目描述
精通程序设计的 Applese 又写了一个游戏。
在这个游戏中,它位于一个 n 行 m 列的方阵中的左上角(坐标为(0, 0),行的序号为0~n?10~n?1,列的序号为0~m?10~m?1)。
现在它想不重复地走过所有格子(除了起点),最后回到左上角的一个方案。
输入描述:
仅一行两个整数 n 和 m,表示方阵的大小。保证大于1×11×1。
输出描述:
如果存在方案,则输出一行操作,包含"L"、"R"、"U"、"D",分别表示左、右、上、下。如果有多种方案,输出任意一种即可。
如果没有方案,则在一行中输出"-1"。
示例2
输入
2 3
输出
RRDLLU
备注:
1≤n,m≤10
正解是模拟构造。用深搜容易爆时间,需要很好地优化。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #define ll long long #define inf 0x3f3f3f3f using namespace std; int d[4][2]={0,1,1,0,0,-1,-1,0};//左下右上 char s[5]="RDLU"; bool vis[12][12]; string res; int n,m,num; bool flag; bool check(int a,int b)//判断是否越界 1*1 到 n*m { if(a>=1 && a<=n && b>=1 && b<=m) return true; else return false; } void dfs(int a,int b,string ans) { if(flag) return;///如果有一种情况符合要求,全局变量flag直接变成true,不要浪费时间继续搜 if(a==1 && b==1 && ans.size()==num) {flag=true;cout<<ans<<endl;return;} for(int i=0;i<4;i++) { int dx=a+d[i][0]; int dy=b+d[i][1]; if( check(dx,dy) && !vis[dx][dy] )//下个点符合要求 { ///ans=ans+s[i];错误的,不应该在外面加,会影响到下一个点的搜索 vis[dx][dy]=true; dfs(dx,dy,ans+s[i]);//进入下一个点深搜 vis[dx][dy]=false;//搜完出来就当作没搜过这个点,尝试其他方向 } } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(vis,false,sizeof(vis)); flag=false; num=n*m; if(num%2) printf("-1\n"); else { dfs(1,1,""); //cout<<res<<endl; if(!flag) printf("-1\n"); } } return 0; }