题目描述

blablabla

样例

blablabla

这个题有点考验思维了。必须好好的理解。
我们要考虑的是最后到终点的距离，终点是（R，C），起点是（0，0）；
注意终点不是最后一个单元格，而是最后一个角（即最后一个单元格的右下角）。
所以，我们并不是按单元格来计算距离，而是按两个直线相交的角来计算。
所以，我的dp[i][j].表示的是（0，0）到（i，j)这个角的最少距离是多少。
同时我们需要考虑的是（0，0）到（i，j）这个角经过的单元格里面的‘/’和‘\’。
想象一下这个过程，如果我要从（0，0）到（1，1）这个角。那我经过的单元格就是Graph[1][1]，同时（0，0）到（1，1）这个角应该是‘\’。所以我们判断一下Graph[1][1]是否等于’\ ‘。如果是，则距离为0，不然为1.
在考虑一下（1，1）到（2，0）这个角。我经过的单元格应该是Graph[2][1]，同时，这个单元格里面的内容应该为’/’。如果是，则距离为0，不然为1.
同理，其他方向。
我们找到其中的规律，并把其作为方向变量即可。
总之一点，不能在像平常那样理解数组下标的意义。
dp[i][j]表示的是角。

最后，这差不多就是一个最短路问题了。
我们每次应该选择距离最小的去不断更新即可。因为这个题，只有两种距离权值（0或者1）。所以我们可以直接用一个双端队列即可。有点dijiskla的思想吧。
同时注意我们不可以直接用vis[i][j]数组来标记是否访问过。
想象一下
dp[i][j] 是0，dp[i-2][j]也是0.
从dp[i][j]到dp[i-1][j+1]的距离为1
从dp[i-2][j]到dp[i-1][j+1]的距离为0.
可是我在更新的时候，更新了dp[i][j]到dp[i-1][j+1].并且把vis[i-1][j+1]标记为访问过了，那我就不会再继续更新dp[i-2][j]到dp[i-1][j+1]了。
因为是双端队列，所以是可能存在这种情况的。

blablabla

时间复杂度分析：blablabla

C++ 代码

#include"stdio.h"
#include"string.h"
#include"deque"
#include"algorithm"
using namespace std;
#define INF 1001010
typedef pair<int,int> PII;

const int dir1[4][2] = {{1,1},{-1,-1},{-1,1},{1,-1}};
const int dir2[4][2] = {{1,1},{0,0},{0,1},{1,0}};
int T,R,C;
char Graph[510][510];
int vis[510][510];
int dp[510][510];
int minx;

int check(int a,int b)
{
     if(a >= 0 && a <= R && b >= 0 && b <= C)
            return 1;
    return 0;
}

void bfs()
{
    deque<PII> Q;
    Q.push_front({0,0});
    vis[0][0] = 1;
    dp[0][0] = 0;
    while(!Q.empty())
    {
        PII T = Q.front(); Q.pop_front();
        int x = T.first,y = T.second;
        for(int i = 0; i < 4; i ++)
        {
            int x1 = x + dir1[i][0],y1 = y + dir1[i][1];
            int a = x + dir2[i][0],b = y + dir2[i][1];
            if(check(x1,y1) == 0) continue;
            int time = (Graph[a][b] != (i <= 1 ? '\\' : '/'));
            if( dp[x1][y1] <= dp[x][y] + time ) continue;
           // vis[x1][y1] = 1;
            dp[x1][y1] = dp[x][y] + time;
            //printf("a = %d b = %d x = %d y = %d x1 = %d y1 = %d dp[x][y] = %d time = %d\n",a,b,x,y,x1,y1,dp[x][y],time);
            if(time == 0)
            Q.push_front({x1,y1});
            else
            Q.push_back({x1,y1});
        }
    }
    return ;
}

int main()
{
    scanf("%d",&T);
    while(T --)
    {
        scanf("%d%d",&R,&C);
        memset(vis,0,sizeof(vis));
        for(int i = 0; i <= R;i ++)
            for(int j = 0; j <= C; j ++)
               dp[i][j] = INF;
        for(int i = 1; i <= R; i ++)
            scanf("%s",Graph[i] + 1);
         bfs();

        if(dp[R][C] == INF)
             printf("NO SOLUTION\n");
        else
            printf("%d\n",dp[R][C]);
    }
}