algorithm - Facebook 黑客杯 : After the Dance Battle

Question

我们想在一个特殊的网格中找到两点之间的最短路径。我们可以一次在相邻的方格之间移动，但我们也可以一次移动在相同类型的单元格(有 10 种类型)之间移动，无论它们之间的距离有多远。

对于最大 100x100 的网格，我们如何找到在两点之间行进所需的步数？

Answer 1

我在比赛中使用 BFS 解决了这个问题。

问题可以建模为图形。每个单元格都是一个节点，并且与每个相邻单元格都有一条边。我们可以通过根据需要计算网格坐标来访问每个单元格及其相邻单元格，而不是显式构建图形，从而简单地保持图形隐式。

每个单元格也有一条到所有相同颜色单元格的边。我们可以通过保留每种颜色的单元格列表并访问与当前单元格颜色相同的所有单元格来将其添加到我们的图形中。

Dijkstra 或 A* 之类的东西可以工作(毕竟它们本质上是一个具有优先级队列/启发式的 BFS)，但为这样一个简单的问题实现它会严重矫枉过正。

代码如下(C++):

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <map> 

using namespace std;

char grid[101][101];
int cost[101][101];

vector<pair<int,int> > colour[10]; // lists of same coloured cells

//used to compute adjacent cells
int dr[]={ 0, 0, 1,-1};
int dc[]={ 1,-1, 0,0};

int rows,cols; // total rows and coloumns


int bfs(pair<int,int> start){
    memset(cost,-1,sizeof(cost)); // all unvisited nodes have negative cost to mark them
    cost[start.first][start.second]=0; // start node has cost 0

    queue<pair<int,int> > Q;
    Q.push(start);

    while (!Q.empty()){

        pair<int,int> node=Q.front();Q.pop();
        int r=node.first;
        int c=node.second;
        int cst=cost[r][c];
        if (grid[r][c]=='E'){
            return cst;
        }

        // search adjacent cells
        for(int i=0;i<4;i++){
            int nr=r+dr[i];
            int nc=c+dc[i];
            if (nr>=0 && nr<rows && nc>=0 && nc<cols && cost[nr][nc]<0 && grid[nr][nc]!='W'){
                cost[nr][nc]=cst+1;
                Q.push(make_pair(nr,nc));
            }
        }

        // search cells of the same colour
        if (grid[r][c]>='1' && grid[r][c]<='9'){
            vector<pair<int,int> > &trans=colour[grid[r][c]-'0'];
            for(int i=0;i<trans.size();i++){
                pair<int,int> next=trans[i];
                if (cost[next.first][next.second]<0){
                    cost[next.first][next.second]=cst+1;
                    Q.push(next);
                }
            }
        }
    }
    return -1;
}

int main(){
    int N;
    cin>>N;
    while(N--){
        cerr<<"cases left"<<N<<endl;
        cin>>rows>>cols;
        pair<int,int> start;
        for(int i=0;i<10;i++) colour[i].clear();

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                cin>>grid[i][j];

                if (grid[i][j]=='S'){
                    start=make_pair(i,j);
                }
                else if (grid[i][j]>='1' && grid[i][j]<='9'){
                    colour[grid[i][j]-'0'].push_back(make_pair(i,j));
                }
            }
        }
        cout<<bfs(start)<<"\n";
    }

    return 0;
}