Did you brush the real title of the blue bridge cup over the years? Come here and teach you to counter attack!

The Blue Bridge Cup registration has begun , Are you ready ？

Before the entry , We must be well prepared , In addition to learning basic knowledge such as algorithms , Also learn to fight .

today , I bring 2017 The real problem of the 2011 Blue Bridge Cup provincial competition , Welcome to do the questions together ~ Poke me alone or move the work Zong number ： Blue bridge cloud class , You can get the Blue Bridge Cup real question bank for free ！（PS： Don't just look without thinking without tapping the code ！）

01 The real problem of the Blue Bridge Cup provincial competition

This question is to fill in the blanks , Just calculate the result , Use the output statement in the code to output the filled results .

X A labyrinth playground on the planet is built on a hillside . It is from 10x10 Made up of interconnected small rooms . There is a big letter on the floor of the room . Let's assume that the player is standing facing uphill , be ：

L Go to the room on the left ;
R Go to the room on the right ;
U It means walking up the slope ;
D It means going downhill .
X The inhabitants of the planet are a little lazy , Not willing to think . They prefer to play games of luck . The same is true of this game ！
At the beginning , Helicopter handle 100 Players into a small room . Players must move according to the letters on the ground .

The map of the maze is as follows ：
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

Please calculate , Last , How many players will walk out of the maze ? Instead of going around in circles .

If you don't understand the rules of the game , See the following simplified 4x4 Explanation of the maze ：

02 Their thinking

（1） Opportunistic

according to “ Note to examinees ”, This question is to fill in the blanks , Just hand in the answer . If you don't want to code , Directly count them one by one with your hands 100 A little bit , It's finished in a few minutes , The answer is 31, Faster than coding .

（2） DFS code

A search question , You can choose dfs, The code is short .

#include <iostream>
using namespace std;
#include<vector>
#include<string>
using namespace std;

int ans;
vector<vector<char>>s={
{'U','D','D','L','U','U','L','R','U','L'},
{'U','U','R','L','L','L','R','R','R','U'},
{'R','R','U','U','R','L','D','L','R','D'},
{'R','U','D','D','D','D','U','U','U','U'},
{'U','R','U','D','L','L','R','R','U','U'},
{'D','U','R','L','R','L','D','L','R','L'},
{'U','L','L','U','R','L','L','R','D','U'},
{'R','D','L','U','L','L','R','D','D','D'},
{'U','U','D','D','U','D','U','D','L','L'},
{'U','L','R','D','L','U','U','R','R','R'}};
bool vis[100][100];
void dfs(int x,int y)
{
if(vis[x][y] == true)
return;
if(x<0||y<0||x>=s.size() || y>=s[x].size())
{
ans++;
return;
}
switch (s[x][y])
{
case 'U':
vis[x][y]= true;dfs(x-1,y);vis[x][y]= false;break;
case 'L':
vis[x][y]= true;dfs(x,y-1);vis[x][y]= false;break;
case 'R':
vis[x][y]= true;dfs(x,y+1);vis[x][y]= false;break;
case 'D':
vis[x][y]= true;dfs(x+1,y);vis[x][y]= false;break;
default:return;
}
}

void has_Path()
{
for(int i=0;i<s.size();++i)
for(int j=0;j<s[i].size();++j)
dfs(i,j);
}

int main()
{
has_Path();
cout<<ans;
}

That's all for today's Blue Bridge Cup real question , In the future, I will update the explanation of the real blue bridge cup from time to time .

If there is any Blue Bridge Cup 、 Code problem , You can also poke me alone , Or step-by-step gongzong number ： Blue bridge cloud class