京東2020算法工程師0824筆試題整理

代碼題：

1：開心消消樂：

#include

#include

#include

#include

#include

#include

#include

#define ll long long

#define inf 0x3f3f3f3f

#define Max 1001 using namespace std; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; string mapp[Max]; int

vis[Max][Max]; int n,m,epoch; int flag; void dfs(int x,int y) {

vis[x][y]=1; if(x0||xn-1||y0||ym-1) {

if(mapp[x][y]mapp[n-x-1][y]||mapp[x][y]mapp[x][m-y-1]) {

flag=1;

return ; } } for(int i=0;i<4;i++) { int dx=x+dir[i][0]; int dy=y+dir[i][1];

if(dx<0||dx>=n||dy<0||dy>=m||vis[dx][dy]||mapp[dx][dy]’#’) continue;

dfs(dx,dy); vis[dx][dy]=0; } } int main() {

cin>>epoch;

while(epoch–){

cin>>n>>m;

for(int i=0;i<n;i++)

cin>>mapp[i];

int st_x,st_y;

for(int i=0;i<n;i++)

{

for(int j=0;j<m;j++)

{

if(mapp[i][j]‘S’)

{

st_x=i;

st_y=j;

}

}

}

flag=0;

dfs(st_x,st_y);

if(flag) cout<<“Yes”<<endl;

else cout<<“No”<<endl;

}  return 0; }
           

2 拼接迷宮： https://blog.csdn.net/qq_40046426/article/details/84930385

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <stack>
#define ll long long
#define inf 0x3f3f3f3f
#define Max 1001
using namespace std;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
string mapp[Max];
int vis[Max][Max];
int n,m,epoch;
int flag;
void dfs(int x,int y)
{
 vis[x][y]=1;
 if(x==0||x==n-1||y==0||y==m-1)
 {
  if(mapp[x][y]==mapp[n-x-1][y]||mapp[x][y]==mapp[x][m-y-1])
  {
    flag=1;
    return ;
  }
 }
 for(int i=0;i<4;i++)
 {
  int dx=x+dir[i][0];
  int dy=y+dir[i][1];
  if(dx<0||dx>=n||dy<0||dy>=m||vis[dx][dy]||mapp[dx][dy]=='#') continue;
  dfs(dx,dy);
  vis[dx][dy]=0;
 }
}
int main()
{
    cin>>epoch;
    while(epoch--){
        cin>>n>>m;
        for(int i=0;i<n;i++)
            cin>>mapp[i];
        int st_x,st_y;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(mapp[i][j]=='S')
                {
                    st_x=i;
                    st_y=j;
                }
            }
        }
        flag=0;
        dfs(st_x,st_y);
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

    }
 return 0;
}