题目大意:给一些棋盘的大小,总格子数不会超过26,。问一个马在棋盘中能不能把整张期盼跑遍,如果能,输出马行走的路线(字典序),如果不能,则输出“impossible”
m*n <= 26...这不是搜索是什么。。。
注意一下输出的时候是按照字典序,先比较字母大小,在比较数字大小。
不要在深搜完之后处理,因为没法处理。在搜索的时候贪心的搜索,现搜号比较小的点,再搜比较大的点,深搜结束的序列就是按照字典序的了。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 30 using namespace std; const int dx[] = {0,-1,1,-2,2,-2,2,-1,1}; const int dy[] = {0,-2,-2,-1,-1,1,1,2,2}; int cases; pair<int,int> ans[MAX]; bool v[MAX][MAX],judge[MAX][MAX]; int m,n; bool finished; inline void Initialize(); void DFS(int x,int y,int step); int main() { cin >> cases; for(int i = 1;i <= cases; ++i) { scanf("%d%d",&m,&n); Initialize(); printf("Scenario #%d:\n",i); ans[1] = make_pair(1,1); v[1][1] = true; DFS(1,1,1); if(!finished) puts("impossible"); putchar('\n'); } return 0; } inline void Initialize() { finished = false; memset(v,false,sizeof(v)); memset(judge,false,sizeof(judge)); for(int i = 1;i <= m; ++i) for(int j = 1;j <= n; ++j) judge[i][j] = true; } void DFS(int x,int y,int step) { if(finished) return ; if(step == m * n) { for(int i = 1;i <= step; ++i) printf("%c%d",ans[i].second + 'A' - 1,ans[i].first); putchar('\n'); finished = true; return ; } for(int i = 1;i <= 8; ++i) { int fx = x + dx[i]; int fy = y + dy[i]; if(judge[fx][fy] && !v[fx][fy]) { ans[step + 1] = make_pair(fx,fy); v[fx][fy] = true; DFS(fx,fy,step + 1); v[fx][fy] = false; } } }