2753   Labyrinth

describe
A maze is made up of R That's ok C It's a grid , There are obstacles in some cells , Can't go ; Some of the lattices are open spaces , You can go .
Given a maze , How many steps does it take to walk from the upper left corner to the lower right corner ( The data guarantee will come to ). You can only walk horizontally or vertically , Don't walk sideways .
Input
The first line is two integers ,R and C, Represents the length and width of the maze .( 1<= R,C <= 40)
Next is R That's ok , Each row C Characters , Representing the whole maze .
Space grid '.' Express , There are obstacles in the grid '#' Express .
The upper left corner and the lower right corner of the maze are '.'.
Output
How many steps does it take for the output to go from the upper left corner to the lower right corner ( That is, at least how many open spaces to go through ). Calculate the number of steps, including the starting point and the ending point .
The sample input
5 5
..###
#....
#.#.#
#.#.#
#.#..
Sample output
9
 #include "bits/stdc++.h"
using namespace std;
const int maxN = ;
const int INF = ;
const int dx [ ] = { , - , , } ;
const int dy [ ] = { , , - , } ;
typedef long long QAQ ; int r , c , ans = INF ; char mp[ maxN ][ maxN ] ;
bool vis[ maxN ][ maxN ] ; void DFS ( const int xi , const int yi , const int step ) {
if ( mp[ xi ][ yi ] == '#' || step > ans ) return ;// When the current answer is worse than the existing one , Don't continue searching
if( xi == r && yi == c ) {
ans = min ( ans , step ) ;
return ;
}
for(int i = ; i < ; ++i ) {
int xx = xi + dx [ i ] ;
int yy = yi + dy [ i ] ;
if ( !vis[ xx ][ yy ] && mp[ xx ][ yy ] == '.' ) { vis[ xx ][ yy ] = true ;
DFS( xx , yy , step + ) ;
vis[ xx ][ yy ] = false ;
}
}
} void Init ( ){
for ( int i= ; i<=r+ ; ++i )
for ( int j= ; j<=c+ ; ++j )
if ( i== || i == r+ || j== || j== c+ ) mp[ i ][ j ] = '#' ;
} int main ( ) {
scanf ( "%d%d" , &r , &c ) ;
Init ( );
getchar ( ) ;
for ( int i= ; i<=r ; ++i ){
for ( int j= ; j<=c ; ++j ) {
mp[ i ][ j ] = getchar ( ) ;
}
getchar ( ) ;
} vis[ ][ ] = true;
DFS ( , , ) ;
cout << ans << endl ;
return ;
}

2016-10-18 18:20:22

( End )

NOI Question bank 2753 More articles about

  1. NOI The question bank swipes the question log ( Greedy chapter )

    This time in NOI There are some questions on the question bank , Let's write some experience and solutions One . Find the maximum point on the plane 2704: Find the maximum point on the plane Total time limit :  1000ms  Memory limit :  65536kB describe On a plane , If there are two points ( ...

  2. NOI Question bank 1768 Maximum submatrix Answer key

    NOI Question bank 1768 Maximum submatrix    Answer key     Total time limit : 1000ms Memory limit : 65536kB   describe   The size of a given matrix is defined as the sum of all elements in the matrix . Given a matrix , Your task is to find the largest non empty ( Big ...

  3. NOI Question bank 09: Image rotation flip transform

    NOI The question at the beginning of the question bank , Also slightly water , Of course, it's also big water , So it's just like that 09: Image rotation flip transform Total time limit : 1000ms Memory limit : 65536kB describe Given m That's ok n Column of the image pixel gray value , Do a series of operations in turn ...

  4. NOI Question bank - Primary school Olympiad QwQ

    today Loli Let's see NOI The Olympic part of the question bank , however , Why primary school ( ⊙ o ⊙ ) ah ! I feel insulted by all kinds of things . The remainder is the same : describe Three positive integers are known a,b,c. There is one greater than 1 The integer of x, Regard it as ...

  5. noi Question bank (noi.openjudge.cn) 1.7 String of programming basis T31——T35

    T31 character string P Type code describe Given a character that is completely composed of numbers ('0','1','2',-,'9') The string formed str, Please write out str Of p Type code string . for example : character string 122344111 It can be described as "1 individual 1.2 individual ...

  6. NOI Question bank 192 Birthday cake

    192: Birthday cake Total time limit : 5000ms Memory limit : 65536kB describe 7 month 17 The day is Mr.W My birthday ,ACM-THU To do this, make a volume of Nπ Of M Layer birthday cake , Each layer is a cylinder . Set the number from bottom to top i ...

  7. NOI Question bank 9272 Answer key

    9272   Even numbers 3 describe Of all the N In figures , How many numbers have even numbers 3? Input One line gives the number N,N<=1000 Output As the title The sample input 2 Sample output 73 Solution : Make f ( ...

  8. noi Question bank (noi.openjudge.cn) 1.5 Cycle control of programming basis T36——T45

    T36 Calculating the value of a polynomial describe Let's assume that the form of the polynomial is xn+xn-1+-+x2+x+1, Please calculate the floating point number of given order precision x And positive integers n In this case, the value of this polynomial . Input Enter only one line , Include x and n, Separate with a single space .x stay flo ...

  9. noi Question bank (noi.openjudge.cn) 1.7 String of programming basis T21——T30

    T21: Word substitution describe Enter a string , End with a carriage return ( String length <=100). The string consists of several words , Words are separated by a space , All words are case sensitive . Now we need to replace one word with another , And output ...

Random recommendation

  1. Notes of Principles of Parallel Programming - TODO

    0.1 TopicNotes of Lin C., Snyder L.. Principles of Parallel Programming. Beijing: China Machine Pres ...

  2. PHP To achieve a simple student information management system (web edition )

    (∩_∩) 1. summary To learn the php Some of the foundations of , Include HTML,php,pdo,mysql Operation etc. , They haven't been combined . Recently wrote a simple web version of student information management system , The front desk with HTML, The script uses JavaScr ...

  3. by Spring add to REST function

    1 About REST I understand it ,REST It is to transfer resources between the server and the client in the most appropriate form . The resources in the system are URL Are identified ( It can be understood as URL Path with parameters ) Use HTTP Methods to manage resources (GET,PUT,P ...

  4. Building a Oracle To Oracle Of Goldengate Two way replication environment

    The goal is : Building a Oracle To Oracle Of Goldengate Two way replication environment ( Support DDL+DML). Environmental Science : OS:Red Hat Enterprise Linux Server release 5.5 ...

  5. margin Vertical overlap

    shorthand : Such as p Vertical of margin yes 16px, So what's the longitudinal distance between the two ?-- As a rule, it should be 16 + 16 = 32px, But the answer is still 16px. Because longitudinal margin It will overlap , Such as ...

  6. from navicat Import sql File is too large. :Got a packet bigger than &#39;max_allowed_packet&#39; bytes

    The background of failure : Just passed navicat To the local mysql Import in database sql file . first sql file ( Multiple tables ) The size is 967M, Successful import : the second sql( A single watch ) The size is 50.1M, Import failed . 1. stay navicat in ...

  7. phpstorm To configure Xdebug debug

    Running environment : PHPSTORM edition : 8.0.1 PHP edition : 5.6.2 xdebug edition :php_xdebug-2.2.5-5.6-vc11-x86_64.dll ps : php Version and xdeb ...

  8. Compressed sensing ( The 21st ): Orthogonal matching pursuit of compressed sensing reconstruction algorithm (OMP)

    primary coverage : OMP Algorithm flow of OMP Of MATLAB Realization Experiments and results of one-dimensional signals Measurements M Experiments and results on the relationship between reconstruction success probability and reconstruction success probability Sparsity K Experiments and results on the relationship between reconstruction success probability and reconstruction success probability One .OMP Algorithm flow of Two .OMP Of MATL ...

  9. Unity3D stay C# Reference and description of some namespace in programming

    System Contains data types used to define common values and references . Events and event handlers . Interface . Properties and exception handling base classes and base classes . Other classes provide services that support the following operations : Data type conversion , Method parameter operation , Mathematical calculation , Remote and local program calls , Application ring ...

  10. Make it super simple bug Management system

    You can try to achieve a super simple bug Management system There is no need to authenticate , That is, there is no need to log in Yes tag management function , Defects can be added with tag, adopt tag distinguish bug The state and type of bug The function of adding, deleting, modifying and checking bug Describe support markdow ...