109徐守佳

用户名：dotcpp0787174

访问量：110

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	5660
经　　验	1485
参赛次数	0
文章发表	15
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	柚子厨

　　自我简介：

TA的其他文章

[信息学奥赛一本通T1471-Phone List] Trie字典树做法
浏览：11

[信息学奥赛一本通T1684-Secret Message 秘密信息] 平平无奇的Trie树
浏览：7

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

[LETTERS] BFS 配合 map容器

　　作者: 109徐守佳　　　　发表时间：2024-09-14 21:50:12 浏览：8　|　评论：1　

原题链接：LETTERS

## unordered_map
的.count函数-用于查找是否出现过该状态,是返回1;
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 1e7 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m;
char g[25][25]; //字符矩阵
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; //方向数组
int ans = -inf; //答案
struct node
{
    int x,y; //该状态的坐标
    unordered_map<char,int> dist; 
	//用于查找该状态是否拿过该字符
    int cnt; //记录该状态拿了多少个字符
};

void bfs()
{
    unordered_map<char,int> stdist; //创立起始的map
    queue<node> q;
    stdist[g[0][0]] = 1; //起始字符标记
    q.push({0,0,stdist,1});
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        ans = max(ans,t.cnt); //时刻更新答案
        for(int i=0;i<4;i++)
        {
            node ne;
            ne.x = t.x + dir[i][0];
            ne.y = t.y + dir[i][1];
            ne.dist = t.dist; //复制上一个状态的unordered_map
            ne.cnt = t.cnt + 1; //拿的字符+1
            if(ne.x < 0 || ne.y < 0 || ne.x >= n || ne.y >=m) continue; //越界叉出去
            if(ne.dist.count(g[ne.x][ne.y])) continue; //已经拿过了叉出去
            ne.dist[g[ne.x][ne.y]] = 1; //记录拿过这个字符了
            q.push(ne);
        }
    }
    
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    bfs();
    cout<<ans;
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

108叶先毅是个小蒟蒻

%%% orz

2024-09-17 01:01:59

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

[LETTERS] BFS 配合 map容器

评论区

精彩推荐

程序员的表白（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

DNA （C语言代码）

C语言训练-8除不尽的数（C语言代码）

字符逆序（C语言代码）

分解质因数（C++代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

[LETTERS] BFS 配合 map容器

评论区

精彩推荐

程序员的表白 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

DNA （C语言代码）

C语言训练-8除不尽的数 （C语言代码）

字符逆序 （C语言代码）

分解质因数 （C++代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

　　评论区

程序员的表白（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

C语言训练-8除不尽的数（C语言代码）

字符逆序（C语言代码）

分解质因数（C++代码）