蓝桥杯2016年第七届真题-路径之谜 （C++代码）

解题思路:

            

参考代码:

#include<bits/stdc++.h>
using namespace std;

const int SIZE = 23;
int Map[SIZE][SIZE];
int Vis[SIZE][SIZE];
int Per[SIZE*SIZE], Step = 1;
int moveX[] = { 1,0,-1,0 },
	moveY[] = { 0,1,0,-1 };
int Mapsize;
bool End;

bool check(int posx, int posy) {
	if (posx >= 1 && posx <= Mapsize && posy >= 1 && posy <= Mapsize)
		if (!Vis[posx][posy] && Map[0][posy] > 0 && Map[posx][0] > 0)
			return true;
	return false;
}

void EndJug(int posx, int posy) {
	if (posx == Mapsize && posy == Mapsize) {
		for (int i = 1; i <= Mapsize; i++)
			if (Map[0][i] != 0 || Map[i][0] != 0)
				return;
		End = true;
	}
}

void DFS(int posx, int posy) {
	if (End) return;
	EndJug(posx, posy);
	if (End) {
		for (int pos = 0; pos < Step; pos++) {
			cout << Per[pos];
			if (pos != Step - 1)
				cout << ' ';
		}
		return;
	}
	for (int i = 0; i < 4; i++) {
		posx += moveX[i]; posy += moveY[i];
		if (check(posx, posy)) {
			Map[0][posy]--; Map[posx][0]--;
			Per[Step++] = Map[posx][posy];
			Vis[posx][posy] = true;

			DFS(posx, posy);

			Vis[posx][posy] = false;
			Map[0][posy]++; Map[posx][0]++;
			Per[Step--] = 0;
		}
		posx -= moveX[i]; posy -= moveY[i];
	}
}

void init() {
	int now = 0;
	for (int i1 = 1; i1 <= Mapsize; i1++)
		for (int i2 = 1; i2 <= Mapsize; i2++)
			Map[i1][i2] = now++;
}

int main() {
	/*ifstream cin("In.txt");*/
	cin >> Mapsize;
	for (int i = 1; i <= Mapsize; i++)
		cin >> Map[0][i];
	for (int i = 1; i <= Mapsize; i++)
		cin >> Map[i][0];
	init();
	Vis[1][1] = true; Map[0][1]--; Map[1][0]--;
	DFS(1, 1);
}