小明的游戏

题目描述

小明最近喜欢玩一个游戏。给定一个 $n \times m$ 的棋盘，上面有两种格子 # 和 @。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是 $0$，否则费用是 $1$。请编程计算从起始位置移动到目标位置的最小花费。

输入格式

输入文件有多组数据。
输入第一行包含两个整数 $n$，$m$，分别表示棋盘的行数和列数。
输入接下来的 $n$ 行，每一行有 $m$ 个格子（使用 # 或者 @ 表示）。
输入接下来一行有四个整数 $x_1, y_1, x_2, y_2$，分别为起始位置和目标位置。
当输入 $n$，$m$ 均为 $0$ 时，表示输入结束。

输出格式

对于每组数据，输出从起始位置到目标位置的最小花费。每一组数据独占一行。

样例 #1

样例输入 #1

2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0

样例输出 #1

2
0

提示

对于20%的数据满足：$1 \le n, m \le 10$。
对于40%的数据满足：$1 \le n, m \le 300$。
对于100%的数据满足：$1 \le n, m \le 500$。

使用双端队列,deque,可以实现队头入队,队尾入队,队头出队,队尾出队.
我们要优先走费用为0的点,所以我们在bfs时,要优先把花费为0的点插到队头,直到没有费用为0的点,我们才去走费用为1的点

#include<iostream>
#include<cstring>
#include<algorithm>
#include<deque>

using namespace std;

typedef pair<int,int> PII;
const int N = 510;
char g[N][N];
//用来记录费用
int dist[N][N];
int n,m;

//x1,y1为起点
//x2,y2为终点
int x1,y1,x2,y2;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int bfs(int x1,int y1,int x2,int y2)
{
    deque<PII> q;
    dist[x1][y1] = 0;
    q.push_back({x1,y1});

    while(!q.empty())
    {
        auto t = q.front();
        q.pop_front();
        char now = g[t.first][t.second];

        for(int i = 0; i < 4; i++)
        {
            int a = t.first + dx[i];
            int b = t.second + dy[i];

            if(a < 0 || b < 0 || a >= n || b >= m) continue;
            if(dist[a][b] != -1 || dist[a][b] == 0) continue;

            if(now == g[a][b])
            {
                q.push_front({a,b});
                //走到相同的点上费用为0
                dist[a][b] = dist[t.first][t.second];
            }
            else
            {
                q.push_back({a,b});
                dist[a][b] = dist[t.first][t.second] + 1;
            }
        }
    }
    return dist[x2][y2];
}

int main()
{
    while(true)
    {
        cin>>n>>m;
        if(n == 0 && m == 0) break;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                cin>>g[i][j];

        cin>>x1>>y1>>x2>>y2;
        memset(dist,-1,sizeof dist);
        int res = bfs(x1,y1,x2,y2);
        cout<<res<<endl;
    }
    return 0;
}