这道题嘛,直接使用DFS搜索,然后莫名其妙地AC了。后来看了题解,说是move的顺序不同的话可能会导致超时,这时便需要剪枝,真是有趣。原来自己是误打误撞AC了,hhh。题解还有另一种解法是先把一条完整的路储存在数组里,输入i的时候,就从i位置起把数组循环输出一遍,真是666的解法呀,果然不能被传统的思路所局限了呀!
#include<bits/stdc++.h>
using namespace std;
int _move[][] ={{, -}, {, -}, {, }, {, },{-, }, {-, }, {-, -}, {-, -}}; struct Node{
int x, y;
vector<int>path;
};
Node node; bool dfs(int x, int y){ node.x = x;
node.y = y;
for(int i = ; i < ; i++){
int x = node.x + _move[i][];
int y = node.y + _move[i][];
if( <= x && x < && <= y && y < ){
int flag = ;
for(int j = ; j < node.path.size(); j++){
if(node.path[j] == x* + y){
flag = ;
break;
}
}
if(flag){
node.path.push_back(x* + y);//走下一步 if(node.path.size() >= ){//当path的size等于30,则说明已经走遍
for(int i = ; i < node.path.size(); i++){
cout << node.path[i] + << ' ';
}
cout << endl;
return true;
}
if(dfs(x, y))return true;
node.path.pop_back();//还原到原来
node.x -= _move[i][];
node.y -= _move[i][];
}
} }
return false;
} int main(){
int n;
while(cin >> n && n != -){
node.path.clear();
n = n-;
int a = n / ;
int b = n % ;
node.path.push_back(a* + b);
dfs(a, b);
}
} /*
#include<iostream>
using namespace std;
int a[]={1,14,25,21,29,18,5,16,12,4,8,19,27,23,10,6,17,30,22,26,13,2,15,7,3,11,24,28,20,9};
int main()
{
int n;
while(cin>>n)
{
int tmp;
for(int i=0;i<30;i++)
if(a[i]==n)tmp=i;
for(int i=0;i<30;i++)
{
cout<<a[(tmp+i)%30];
if(i==29)cout<<endl;
else cout<<" ";
}
}
}
*/