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

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<iterator>

#include<stdio.h>

#include<iomanip>

#include<string>

#include<cstring>

#include<string.h>

#include<vector>

#include<algorithm>

#include<stdio.h>

#include<math.h>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<queue>

#include<sstream>

using namespace std;

int n;

int num[21][21];

int v[21][21];

int Move[4][2] = { {0,-1},{1,0},{0,1},{-1,0} };

deque<int> sum;

int xnum[21];

int ynum[21];

int testx[21];

int testy[21];

deque<int> ans;

bool check()

{

bool flag=true;

for(int i=0;i<n;i++)

if (xnum[i] != testx[i])

{

flag = false;

return flag;

}

for (int i = 0; i < n; i++)

if (ynum[i] != testy[i])

{

flag = false;

return flag;

}

return flag;

}

void bfs(int x, int y)

{

sum.push_back(num[x][y]);

if (x == n - 1 && y == n - 1)

{

if(check())

ans = sum;

return;

}

for (int i = 0; i < 4; i++)

{

int itemp, ytemp;

itemp = x + Move[i][0];

ytemp = y + Move[i][1];

if (itemp != -1 && itemp != n && ytemp != -1 && ytemp != n && v[itemp][ytemp] != 1)

{

testx[itemp]++;

testy[ytemp]++;

v[itemp][ytemp] = 1;

bfs(itemp, ytemp);

sum.pop_back();

v[itemp][ytemp] = 0;

testx[itemp]--;

testy[ytemp]--;

}

}

}

int  main()

{

cin >> n;

for (int i = 0; i < n; i++)

cin >> ynum[i];

for (int j = 0; j < n; j++)

cin >> xnum[j];

int flag = 0;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

num[i][j] = flag;

flag++;

}

}

v[0][0] = 1;

testx[0] = 1;

testy[0] = 1;

bfs(0, 0);

while (!ans.empty())

{

cout << ans.front()<<" ";

ans.pop_front();

}

return 0;

}