题目链接:https://ac.nowcoder.com/acm/contest/330/B
数据范围只有10*10,所以可以用搜索写,模拟也可以就是感觉有点麻烦,首先我们要知道对于n和m都是奇数的话是走不通的(还有就是1*2是可以走的,1*4是不能走的这种情况),然后我们在纸上画一下,就很容易发现它走的规律,先判断奇偶性,优先先往偶数边走(具体就不细讲了,自己画画图就好了),下面把两种方法的code都贴上。
AC代码(模拟):
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
scanf("%d %d",&n,&m);
if(n % 2 == 0){
for(int i=0;i<n-1;i++) printf("D");
for(int i=0;i<m-1;i++) printf("R");
printf("U");
for(int i=0;i<n-2;i++){
for(int j=0;j<m-2;j++)
printf("%c", i % 2 ? 'R' : 'L');
printf("U");
}
for(int i=0; i<m-1; i++)
printf("L");
}
else if(n == 1 && m >= 3) puts("-1");
else if(m == 1 && n >= 3) puts("-1");
else if(m % 2 == 0){
for(int i=0;i<m-1;i++) printf("R");
for(int i=0;i<n-1;i++) printf("D");
printf("L");
for(int i=0;i<m-2;i++){
for(int j=0; j<n-2; j++)
printf("%c", i % 2 ? 'D' : 'U');
printf("L");
}
for(int i=0; i<n-1; i++)
printf("U");
}
else printf("-1");
return 0;
}
AC代码(dfs):
#include <bits/stdc++.h>
#define maxn 15
using namespace std;
bool vis[maxn][maxn];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
string s = "DRUL";
string str;
bool flag;
int n,m;
bool Check(int x,int y){
if(x >= 0 && y >= 0 && x < n && y < m && vis[x][y] == false)return true;
return false;
}
void dfs(int x,int y,string a){
cout<<x<<" "<<y<<endl;
if(x == 0 && y == 0 && a.length() == n * m){
str = a;
flag = true;
return ;
}
for(int i=0;i<4;i++){
int X = x + dir[i][0];
int Y = y + dir[i][1];
if(Check(X, Y)){
vis[X][Y] = true;
dfs(X, Y, a + s[i]);
vis[X][Y] = false;
if(flag) return ;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
if(n % 2 && m % 2 && n != 1 && m != 1){
puts("-1");
return 0;
}
memset(vis, false, sizeof(vis));
flag = false;
dfs(0, 0, "");
if(flag) cout<<str<<endl;
else puts("-1");
return 0;
}