Informatics Aosai yibentong 1212: letters | openjudge 2.5 156: Letters

【 Topic link 】

ybt 1212：LETTERS
OpenJudge 2.5 156:LETTERS

【 Topic test site 】

1. Deep search

set up bool type vis Array , The length is 128.vis[i] True means ascii Code for i The letters of have been visited .
Set variables step Record the number of letters that have been accessed ,mx Record the maximum number of letters accessed .
Every time you traverse to a location , Search its four positions up, down, left and right , If this location is on the map , And the character in this position has not been accessed , Then change the access status of letters , Include vis Array and step Variable （ Update here step Maximum mx）, Then search this new location . After searching , Remember to restore the state .
The specific writing of deep search , Have access to... Before function call , And access in function calls , The only difference is whether the position passed in as a parameter is in the accessed state inside the function .

【 Solution code 】

How to write it 1： Access... Before a function call

#include <bits/stdc++.h>
using namespace std;
#define N 25
int r, s, step, mx;
char mp[N][N];
bool vis[128];
int dir[4][2] = {
    {
    0,1},{
    0,-1},{
    -1,0},{
    1,0}};
void dfs(int sx, int sy)// Access... Before a function call  
{
    
    for(int i = 0; i < 4; ++i)
    {
    
        int x = sx + dir[i][0], y = sy + dir[i][1];
        if(x >= 1 && x <= r && y >= 1 && y <= s && vis[mp[x][y]] == false)
        {
    
            vis[mp[x][y]] = true;// Update status  
            step++;
            mx = max(step, mx);
            dfs(x, y);
            step--;// State restoration  
            vis[mp[x][y]] = false;
        }
    }
}

int main()
{
    
    cin >> r >> s;
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= s; ++j)
            cin >> mp[i][j];
    vis[mp[1][1]] = true;// Access the initial location  
    step = 1;
    mx = 1;
    dfs(1,1);
    cout << mx;
    return 0;
}

How to write it 2： Access... Within a function call

#include <bits/stdc++.h>
using namespace std;
#define N 25
int r, s, step, mx;
char mp[N][N];// Map  
bool vis[128];//vis[i]:ascii Code for i Whether the letters of have been accessed  
int dir[4][2] = {
    {
    0,1},{
    0,-1},{
    -1,0},{
    1,0}};// Direction array  
void dfs(int sx, int sy)// Access... Within a function call  
{
    
	if(sx >= 1 && sx <= r && sy >= 1 && sy <= s && vis[mp[sx][sy]] == false)// If (sx,sy) In the map and the letters at that location have not been visited  
    {
    
    	vis[mp[sx][sy]] = true;// Access the letter  
        step++;// Move steps plus 1 
        mx = max(step, mx);// Update Max  
	    for(int i = 0; i < 4; ++i)// Search up, down, left and right  
	    {
    
	        int x = sx + dir[i][0], y = sy + dir[i][1];
	        dfs(x, y);
	    }
	    step--;// State restoration  
	    vis[mp[sx][sy]] = false;
	}
}
int main()
{
    
    cin >> r >> s;
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= s; ++j)
            cin >> mp[i][j];
    dfs(1,1);
    cout << mx;
    return 0;
}