求解一道C++试题

#include
#include
#include
#include
#include
using namespace std;
char G[1010][1010];
bool vis[1010][1010];
int S[1010][1010];
int n,m;
struct Node{
    int x,y,step;
    Node(int x=0,int y=0,int step=0):x(x),y(y),step(step){}
    bool operator < (const Node &rhs) const{
        return step>rhs.step;
    }
};
priority_queueQ;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
bool work(int x_1,int y_1,int x_2,int y_2,int k){
    while(!Q.empty())Q.pop();
    memset(vis,0,sizeof(vis));
    memset(S,0x3f3f,sizeof(S));
    if(G[x_1][y_1]=='1'){
        Q.push(Node(x_1,y_1,0));
        S[x_1][y_1]=0;
    }else{
        Q.push(Node(x_1,y_1,1));
        S[x_1][y_1]=0;
    }
    if(x_1==x_2 && y_1==y_2){
        Node t=Q.top();
        if(t.step<=k) return true;
        return false;
    }
    while(!Q.empty()){
        Node now=Q.top();
        int step=now.step;
        Q.pop();
        if(vis[now.x][now.y]!=0) continue;
        vis[now.x][now.y]=1;
        for(int i=0;i<4;i++){
            int tx=now.x+dir[i][0],ty=now.y+dir[i][1];
            if(tx<1 || ty<1 || tx>n || ty>m || vis[tx][ty]==1) continue;
            if(G[tx][ty]=='1'){
                Q.push(Node(tx,ty,step));
                S[tx][ty]=min(S[tx][ty],step);
            }
            else{
                Q.push(Node(tx,ty,step+1));
                S[tx][ty]=min(S[tx][ty],step+1);

            }
        }
    }
    if(S[x_2][y_2]>k) return false;
    return true;
}
int main(){
    ifstream fin("design.in");
    ofstream fout("design.out");
    fin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            fin>>G[i][j];
            if(G[i][j]==0) cnt++;
        }
    int q;
    fin>>q;
    for(int i=0;i        int x_1,x_2,y_1,y_2,k;
        fin>>x_1>>y_1>>x_2>>y_2>>k;

        if(!work(x_1,y_1,x_2,y_2,k) || k>cnt)
            fout<<"No"<        else
            fout<<"Yes"<    }
    fout.close();
    fin.close();
    return 0;
}

if(count = mm.count(1))
{
//1.如果要使用,还是得使用equal_range查找一次.
//multimap没有[]操作符重载,因为key不是唯一.
//输出 mm.count(1): 3
cout << "mm.count(1): " << count << endl;
}

//查看下count的实现,是使用equal_range来实现的.
//equal_range是获取所有等于key的value组成一个连续的iterator,
//其中pair第一个是匹配key的第一个iterator,第二个是大于key的第一个iterator.
//map
pair values = m.equal_range(1);
TMap::iterator b = values.first;
//输出 map equal_range: 8
while(b != values.second)
{
cout << "map equal_range: " << (*b).second << endl;
++b;
}

这个用一个深度搜索或者广度搜索很容易搞定，把从起点开始的每一个岔路（可以直接去的临近元素）放到栈或者队列中，然后重复过程。
因为不是找最近路，只是问能不能走到，所以不难。
不过这个题目出的人倒是挺酸的。

相当于起点到终点求最短路径。将地图抽象为有向图，正常边权为0，进入“荆棘”的边权为1。