京东笔试第一题分享:

由于方格比较小,就采用暴力破解的方法,注意一下中间变量的保存就行了,方法比较笨,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;
}

#京东#

京东笔试消消乐

全站热榜