2022 Zhengzhou light industry Freshmen's competition topic - I won't say if I'm killed

7-5 Kill me without saying ！ (15 branch )

stem ： What is the best secret code ？ yes “ Kill me without saying ！” such , Even if the pig teammate who helped us transmit the secret code was caught by the enemy and tortured , We don't have to worry about divulging secrets .

Now improve a little , We put “ Kill me without saying ” The first letter of Pinyin “DSWYBS” Hidden in a matrix , On behalf of “ hit ” The letter of D And representatives “ say ” The letter of S The sum of the subscripts in the row is the password .

For a given matrix , Please judge whether there is “DSWYBS”, If there is , Give the subscript of the first and last two letters and calculate the password ; without , Print a row “DSWYBS”.

Be careful :

1. If hidden “DSWYBS”, Then this string of letters must be along the line 、 Column or oblique 45 Degrees in order .
2. The title ensures that the input matrix contains at most one string “DSWYBS”.
3. The subscript in the upper left corner of the matrix is （0,0）.
4. Case sensitive .
5. The title ensures that the input matrix does not contain such an arrangement （ namely ： have only DSWYB Five letters , But the letters B And S adjacent , It can be made up of DSWYBS Permutation ） ：

DSB
 WY

Input format ：
The first line gives two integers M、N（ No more than 15、 Not less than 4）, Next M That's ok , Each row has N Letters or numbers , End with a new line .

Output format ：
If there is “DSWYBS”, Then output three lines , The first and second lines are initials respectively D Subscript and final letter of S The subscript , First subscript then column subscript , Separated by a space . The third line gives the sum of the four subscript values of two letters .

If the string of letters is not hidden , Then print a line “DSWYBS”

sample input

8 10
0x00z000d0
00aD00s000
00b0SWk000
000wcY000s
00000B0000
0000S00000
0000000000
0000000000

sample output

1 3
5 4
13

sample input

5 5
12345
adswa
54321
dswys
aaaaa

sample output

DSWYBS

Topic analysis ：

1. dfs Traverse

The code is as follows ：

#include<bits/stdc++.h>
using namespace std;
string s="DSWYBS";
int m,n;
char a[16][16];
bool vis[16][16]={false};
bool flag=false;
int fx,fy,lx,ly;
void dfs(int x,int y,int count){
    // As of condition 
    if(flag==true||count==6){
        flag=true;
        lx=x;
        ly=y;
        return;
    }

    // Traversing candidate nodes 
    for(int i=x-1;i<=x+1;i++){
        for(int j=y-1;j<=y+1;j++){
            // Screening 
            if(i>=0&&i<m&&j>=0&&j<n){
                if(!vis[i][j]&&a[i][j]==s[count]){
                    // cout<<count<<" "<<s[count]<<" "<<i<<" "<<j<<endl;
                    vis[i][j]=true;
                    dfs(i,j,count+1);
                    vis[i][j]=false;
                }
            }
        }
    }
}
int main(){
    // freopen("in.txt","r",stdin);

    cin>>m>>n;
    getchar();
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!vis[i][j]&&a[i][j]==s[0]){
                vis[i][j]=true;
                int x=fx;
                int y=fy;
                fx=i;
                fy=j;
                dfs(i,j,1);
                if(flag==true){
                    break;
                }
                fx=x;
                fy=y;
                vis[i][j]=false;
            }
        }
    }
    if(flag==true){
        int sum=0;
        sum=fx+fy+lx+ly;
        cout<<fx<<' '<<fy<<endl<<lx<<' '<<ly<<endl<<sum;
    }else{
        cout<<"DSWYBS";
    }
    
    
    
    return 0;
}