题解 | abc431 | # E - Reflection on Grid #

思路：双端队列广搜

题面：

There is a grid with H rows and W columns. We will refer to the cell at the i-th row from the top and j-th column from the left as cell (i,j). Each cell has at most one mirror placed on it.

Takahashi is standing on the left side of cell (1,1), and Aoki is standing on the right side of cell (H,W). Takahashi has a flashlight and is shining light from the left side of cell (1,1) toward the right. Here, assume that the flashlight's light does not diffuse and is a light ray that travels straight.

Takahashi's goal is to deliver the flashlight's light to Aoki by using the mirrors in the grid.

There are three types of mirror placements. When light hits a mirror, the direction of the light changes according to the mirror placement. For each mirror placement, the exit direction for each entry direction is as shown in the figures below.

• type A (no mirror is placed)

• type B (a mirror is placed on the diagonal connecting the upper-left and lower-right)

• type C (a mirror is placed on the diagonal connecting the upper-right and lower-left)

The mirror placement on the grid is represented by H strings of length W:S1 ​ ,S2 ​ ,…,SH ​ . When the j-th character of Si is A, cell (i,j) is type A; when it is B, cell (i,j) is type B; when it is C, cell (i,j) is type C.

Takahashi can perform the following operation any number of times to deliver the light to Aoki:

Choose one cell and change the mirror placement of that cell to a different type. Find the minimum number of operations needed to deliver the light to Aoki.

You are given T test cases; find the answer for each.

using namespace std;

struct state{//存储一个格子中的状态，注意需要存储在这个格子中的光线方向
    int x, y, direction;
    state(int x, int y, int d):x(x), y(y), direction(d){}
};

int t, h, w;
const int INF = 0x3f3f3f3f;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};//上右下左
//将更新后光线的方向与下一个要走到的格子方向对应

int reflect(int d, char type){
    if(type == 'A') return d;
    if(type == 'B'){
        if(d == 0) return 3;
        if(d == 1) return 2;
        if(d == 2) return 1;
        return 0;
    }
    if (type == 'C') {
        if (d == 0) return 1;
        if (d == 1) return 0;
        if (d == 2) return 3;
        return 2;
    }
    return -1;
}

int bfs(vector<vector<char>>& g){
    vector<vector<vector<int>>> dist(h, vector<vector<int>>(w, vector<int>(4, INF)));
    vector<vector<vector<bool>>> vis(h, vector<vector<bool>>(w, vector<bool>(4, false)));
    deque<state> q;
    q.push_back({0, 0, 1});
    dist[0][0][1] = 0;
    int ans = INF;
    while(q.size()){    
        auto t = q.front();
        q.pop_front();
        int x = t.x, y = t.y, d = t.direction;
        if(vis[x][y][d]) continue;
        vis[x][y][d] = true;
        for(char type : {'A', 'B', 'C'}){
            int cost = (type == g[x][y]) ? 0 : 1;
            int new_dir = reflect(d, type);
            int nx = x + dx[new_dir], ny = y + dy[new_dir];

            //是因为最后一个格子中还可能有镜子，所以需要最后一次更新方向，仍然合适才可以
            if(x == h - 1 && y == w - 1 && new_dir == 1){ //在出队，且更新完方向后判断
                ans = min(ans, dist[h - 1][w - 1][d] + cost);
            }

            if(nx >= 0 && nx < h && ny >= 0 && ny < w){
                if(dist[x][y][d] + cost < dist[nx][ny][new_dir]){
                    dist[nx][ny][new_dir] = dist[x][y][d] + cost;
                    
                    if(cost == 0) q.push_front({nx, ny, new_dir});
                    else q.push_back({nx, ny, new_dir});
                }
            }
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--){
        cin >> h >> w;
        vector<vector<char>> g(h, vector<char>(w));
        for(int i = 0;i < h;i++)
            for(int j = 0;j < w;j++) cin >> g[i][j];

        cout << bfs(g) << endl;
    }
    return 0;
}