Question

求解一道C++试题

2. 落梅风(design.pas/c/cpp)
——落花水香茅舍晚，断桥头卖鱼人散。
【问题描述】
伊喜欢赏花。
不为那万花竞放的繁华，只为那蓦然回首的阑珊。
伊要采一朵花，比生还优美，比死还贞洁。
这朵花静静地躺在秘境中，伊现在知道了这个秘境的地图。秘境是一块 n*m 的方格地，
每块土地可能是荆棘或空地。由于秘境的特殊性，伊需要每次从(x1,y1)走到(x2,y2)来完成考
验。因为荆棘是不能走的，秘境之灵每次可以为伊恰好拆除 k 块荆棘地，伊可以决定拆哪些
荆棘。伊要完成 q 次考验，现在你的任务就是对于每次考验，告诉伊能不能成功地完成。
玫瑰花的葬礼。伊捧着花儿，却已泣涕涟涟。
【输入】
输入文件 design.in 的第一行有 2 个用空格隔开的整数 n 和 m。
接下来 n 行是一个 n*m 的矩阵，矩阵中第 i 行 j 列的字符表示第 i 行 j 列的土地是荆棘
还是空地，荆棘为 0，空地为 1。
接下来一行为一个正整数 q。
接下来 q 行每行 5 个正整数 x1,y1,x2,y2,k。
【输出】
输出文件 design.out 共 q 行，若第 i 次考验能完成则输出“Yes” ，否则输出“No” 。
【输入输出样例】
design.in design.out
5 5
01000
11111
10101
00000
11111
4
1 1 3 4 1
2 2 2 4 0
5 1 1 5 1
1 1 5 5 15
No
Yes
No
No
【数据范围】
30%的数据满足：1<=n,m<=10
70%的数据满足：1<=n,m<=200
100%的数据满足：1<=n,m<=1000,1<=q<=10,1<=x1,x2<=n,1<=y1,y2<=m,1<=k<=52501

Answer 1

#include<iostream>
#include<algorithm>
#include<fstream>
#include<cstring>
#include<queue>
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_queue<Node>Q;
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<q;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"<<endl;
        else
            fout<<"Yes"<<endl;
    }
    fout.close();
    fin.close();
    return 0;
}

追问

谢谢，可惜回答的晚了，没采纳你的，望原谅

Answer 2

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<TMap::iterator,TMap::iterator> 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;
}

Answer 3

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

Answer 4

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