T02488: A Knight's Journey

backtracking, http://cs101.openjudge.cn/practice/02488/

思路：dfs暴力求解，没有一点剪枝，一遍ac，用时约30min

#include <iostream>
#include <map>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

const vector<pair<int,int>> directions = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

class Solution
{
	public:
		int row , col;
		vector<vector<bool>> isVisited;
		bool isFind;
		vector<pair<int,int>> path;
		int step;
		int curX, curY;

		void initialize()
		{
			cin >> col >> row;
			isVisited.resize(row,vector<bool>(col,false));
			isFind = false;
			path.clear();
            step = 0;
			curX = curY = 0;
		}

		bool isInBoard(int x, int y)
		{
			return (x >= 0 && x < row && y >= 0 && y < col);
		}

		void findPath( )
		{
            if(isFind) return;
            if(!isInBoard(curX,curY)) return;
            if(isVisited[curX][curY]) return;
			if (step == row * col - 1)
			{
                isFind = true;
                path.push_back({curX,curY});
                return;
			}
           
			for (auto dir : directions)
			{
				isVisited[curX][curY] = true;
				path.push_back({ curX,curY });
                curX += dir.first;
                curY += dir.second;
                step++;
                findPath();
                if (isFind) return;
				step--;
				curX -= dir.first;
                curY -= dir.second;
				path.pop_back();
				isVisited[curX][curY] = false;
			}
			
		}

		void solve()
		{
			for (int curX = 0; curX < row; curX++)
			{
				for (int curY = 0; curY < col; curY++)
				{
					if(isFind) return;
                    findPath();
				}
			}
		}

		void printAns()
		{
			solve();
			if (isFind)
			{
				for (auto p : path)
					cout << char(p.first + (int)'A') << p.second + 1;
			}
			else
				cout << "impossible" ;
		}
};

int main()
{
	int n;
    cin >> n;
	for (int i = 0; i < n; i++)
	{
		Solution s;
        s.initialize();
		if (i) cout << endl;
		cout <<"Scenario #"<< i + 1 << ":" << endl;
        s.printAns();
        cout << endl;
	}
	return 0;
}