京东笔试消消乐
京东笔试第一题分享:
由于方格比较小,就采用暴力破解的方法,注意一下中间变量的保存就行了,方法比较笨,minNum初始化为格子大小25(最多)
//first problem
void show(int **graph)
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
cout << graph[i][j] << "*";
}
cout << endl;
}
cout << "*********" << endl;
return;
}
vector<pair<int,int>> cluster(int **graph, int N=5,int M=5)
{
vector<pair<int,int>> ret;
// show(graph);
vector<pair<int,int>> point;
int x, y;
pair<int,int> temp;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (graph[i][j] != -1)
{
temp.first = i;
temp.second = j;
int count = 1;
int index = graph[i][j];
graph[i][j] = -1;
point.clear();
point.push_back(temp);
int xx = i;
int yy = j;
while (point.size() > 0)
{
temp = point.back();
point.pop_back();
x = temp.first;
y = temp.second;
if (x > 0 && graph[x - 1][y] == index)
{
graph[x - 1][y] = -1;
count++;
point.push_back({x - 1, y});
}
// cout<<x<<"*"<<graph[4][2]<<endl;
if (x < N-1 && graph[x + 1][y] == index)
{
graph[x + 1][y] = -1;
count++;
point.push_back({x + 1, y});
}
if (y > 0 && graph[x][y - 1] == index)
{
graph[x][y - 1] = -1;
count++;
point.push_back({x, y - 1});
}
if (y < M-1 && graph[x][y + 1] == index)
{
graph[x][y + 1] = -1;
count++;
point.push_back({x, y + 1});
}
}
if (count > 2)
{
ret.push_back(temp);
}
}
}
}
return ret;
}
void label(int **graph, pair<int,int> position,int N=5,int M=5)
{
vector<pair<int,int>> point;
pair<int,int>temp;
point.push_back(position);
int index = graph[position.first][position.second];
int x, y;
// cout << position[0] << "*" << position[1] << "*" << index << endl;
while (point.size() > 0)
{
temp = point.back();
point.pop_back();
x = temp.first;
y = temp.second;
graph[x][y] = -1;
if (x > 0 && graph[x - 1][y] == index)
{
graph[x - 1][y] = -1;
point.push_back({x - 1, y});
}
if (x < N-1 && graph[x + 1][y] == index)
{
graph[x + 1][y] = -1;
point.push_back({x + 1, y});
}
if (y > 0 && graph[x][y - 1] == index)
{
graph[x][y - 1] = -1;
point.push_back({x, y - 1});
}
if (y < M-1 && graph[x][y + 1] == index)
{
graph[x][y + 1] = -1;
point.push_back({x, y + 1});
}
}
return;
}
void fall(int **&graph,int N=5,int M=5)
{
for (int i = N-2; i >= 0; i--)
{
for (int j = 0; j < M; j++)
{
if (graph[i][j] != -1 && graph[i + 1][j] == -1)
{
int k = i;
while (k < N-1 && graph[k + 1][j] == -1)
k++;
graph[k][j] = graph[i][j];
graph[i][j] = -1;
}
}
}
return;
}
int count(int **graph,int N=5,int M=5)
{
// show(graph);
int ret = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (graph[i][j] != -1)
ret++;
}
}
return ret;
}
void entertainment(int **graph, int &minNum, int N=5,int M=5)
{
// show(graph);
int **dataArray = (int **)malloc(sizeof(int *)*N);
for (int i = 0; i < N; i++)
dataArray[i] = new int[5];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
dataArray[i][j] = graph[i][j];
}
}
vector<pair<int,int>> ret = cluster(dataArray,N,M);
if (ret.size() == 0)
{
int temp = count(graph,N,M);
if (temp < minNum)
minNum = temp;
return;
}
for (int i = 0; i < ret.size(); i++)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
dataArray[i][j] = graph[i][j];
}
}
pair<int,int> position = ret[i];
// show(dataArray);
label(dataArray, position,N,M);
// show(dataArray);
fall(dataArray,N,M);
// show(dataArray);
// cout<<position[0]<<position[1]<<graph[position[0]][position[1]]<<endl;
entertainment(dataArray, minNum,N,M);
}
return;
} 第二题,迷宫求解: 讲输入当成一个格子,复制一个3*3的格子,再用dfs判断有没有路径到边缘即可.
bool findPath(vector<string >& grid, vector<vector<bool > >& vis, int y, int x)
{
if (y == -1 || y == grid.size() || x == -1 || x == grid[0].size())
return true;
if (vis[y][x] || grid[y][x] == '#')
return false;
vis[y][x] = true;
if (findPath(grid, vis, y - 1, x) || findPath(grid, vis, y + 1, x) || findPath(grid, vis, y , x - 1) || findPath(grid, vis, y, x+1))
return true;
return false;
}
int girdPath()
{
int t;
cin >> t;
for (int k = 0; k < t; k++)
{
int m, n;
cin >> m >> n;
vector<string > grid(m);
for (int i = 0; i < m; i++)
cin >> grid[i];
// copy 3*3
vector<string > bigGrid(3 * m);
for (int i = 0; i < m; i++)
{
bigGrid[i] = grid[i] + grid[i] + grid[i];
bigGrid[m + i] = bigGrid[i];
bigGrid[2*m + i] = bigGrid[i];
}
// find start point
int i, j;
bool find = false;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (grid[i][j] == 'S')
{
find = true;
break;
}
}
if (find)
break;
}
// find path
vector<vector<bool>> vis(3 * m);
for (int i = 0; i < 3 * m; i++)
vis[i] = vector<bool >(3 * n, false);
if (findPath(bigGrid, vis, m + i, n + j))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
} 
投递字节跳动等公司9个岗位
