CCF 2013 12-5 I’m stuck

9/5/2021 6:02:16 PM

subject

Problem description

Given a R That's ok C Column map , Every square of the map could be ’#’, ‘+’, ‘-’, ‘|’, ‘.’, ‘S’, ‘T’ One of the seven characters , They mean the following ：
　　‘#’: Players cannot move to this square at any time ;
　　‘+’: When the player reaches this square , In the next step, you can move up, down, left, right and any adjacent non ’#‘ Move one square ;
　　‘-’: When the player reaches this square , In the next step, you can move to a non adjacent one in the left and right directions ’#‘ Move one square ;
　　‘|’: When the player reaches this square , In the next step, you can move up and down the adjacent non ’#‘ Move one square ;
　　‘.’: When the player reaches this square , You can only move down one grid in the next step . If the adjacent square below is ’#’, Then the player can no longer move ;
　　‘S’: The player's initial position , There will only be one initial location in the map . When the player reaches this square , In the next step, you can move up, down, left, right and any adjacent non ’#‘ Move one square ;
　　‘T’: The player's target location , There will only be one target location in the map . When the player reaches this square , You can choose to complete the task , You can also choose not to complete the task and continue to move . If you continue to move, the next step can be up, down, left, right and any adjacent non ’#' Move one square .
　　 Besides , Players cannot move out of the map .
　　 Please find the number of squares that satisfy the following two properties ：
　　1. Players can move from their initial position to this square ;
　　2. Players cannot move from this square to the target position .

Input format

The first line of input contains two integers R and C, Respectively represent the number of rows and columns of the map .(1 ≤ R, C ≤ 50).
　　 Next R Each line contains C Characters . They represent the grid of the map . There happens to be one on the map ’S’ And a ’T’.
### Output format
　　 If the player is in the initial position, he can't reach the end , It outputs “I’m stuck!”（ No double quotes ）. Otherwise , Output the number of squares satisfying properties .

The sample input

5 5
--+-+
..|#.
..|##
S-+-T
####.

Sample output

2

Sample explanation

If you use the square satisfying the property on the map ’X’ If marked , The map is shown below ：

–±+

…|#X

…|##

S-±T

####X

Answer key :

Key Word : graph theory 、 Pros and cons DFS

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

const int maxn = 55;
int row,col;
int tx,ty;// End coordinates 
int sx,sy;// Starting point coordinates 
char G[maxn][maxn];

int cons1[maxn][maxn],cons2[maxn][maxn];
//cons [i][j] = 1  Express i That's ok j Column   It can reach 

int dx[4] = {
    -1,0,1,0},dy[4] = {
    0,1,0,-1};

//  Judge the current point （x,y） Can I go 
// k  Indicates direction , use 0~3 Express 
bool check(int x, int y , int k){
    
    char c = G[x][y];
    //  You can walk up, down, left and right 
    if(c == '+' || c == 'S' || c == 'T') return true;
    //  You can only walk left and right ,k by 1 perhaps 3, Odd number 
    if(c == '-' && k %2 == 1) return true;
    //  You can only walk up and down ,k by 0 or 2, Even number 
    if(c == '|' && k % 2 == 0) return true;
    //  You can only go down ,k by 2
    if( c == '.' && k == 2)  return true;
    //  In other cases, you can't go 
    return false;
}



void dfs1(int x,int y){
    
    cons1[x][y] = 1;
    for(int i=0;i<4;i++){
    
        int xx = x + dx[i],yy = y + dy[i];
        if(xx <0 || xx >= row || yy <0 || yy >= col || G[xx][yy] == '#') 
            continue;
        if(cons1[xx][yy]) continue;
        if(check(x,y,i)) dfs1(xx,yy);
    }
}

void dfs2(int x,int y){
    
    cons2[x][y] = 1;
    for(int i=0;i<4;i++){
    
        int xx = x + dx[i],yy = y + dy[i];
        if(xx <0 || xx >= row || yy <0 || yy >= col || G[xx][yy] == '#') 
            continue;
        if(cons2[xx][yy]) continue;
        if(check(xx,yy,i^2)) dfs2(xx,yy);
    }
}

int main()
{
    
    cin >> row >> col;
    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
        {
    
            cin>>G[i][j];
            if(G[i][j] == 'T')
            {
    
                    tx = i; ty = j;
            }
            if(G[i][j] == 'S')
            {
    
                    sx = i; sy = j;
            }
        } 
    // Traverse from the starting point  
    dfs1(sx,sy);
    // Traverse backward from the end point 
    dfs2(tx,ty);

    if(cons1[tx][ty] == 0)
        cout<<"I'm stuck!";
    else{
    
        int ans = 0;
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++){
    
                if(cons1[i][j] && !cons2[i][j])
                    ans ++;
            }
            cout << ans <<"\n";
    }
    
    return 0;
}

understand ：

The first is graph theory Inside the classic part dx dy Application And use this to determine the direction

after DFS Writing And cleverly use the reverse DFS
DFS The reachable range is determined And mark Finally come to the answer ！