Luogu神牛辣么多,怎么可能不会
~~别指望我,昨天刚学bfs~~
@[qhdx_zzd](/user/825829)
by _Adolf_Hitler_ @ 2023-07-18 18:53:33
@[qhdx_zzd](/user/825829) 这道题感觉数据范围不是很明确,因为题上没有说棋盘的大小范围,你把这一行
```cpp
if(!mark[dx][dy] && dx >= 1&&dx <= n&&dy>=1&&dy <= m)
```
的边界条件改大一点就能过了
by Brilliant11001 @ 2023-07-18 18:57:35
@[Brilliant11001](/user/602372) 谢谢你
by qhdx_zzd @ 2023-07-19 10:45:09
@[Brilliant11001](/user/602372) 变成五十分了
```cpp
#include<bits/stdc++.h>
#define int long long
#define i64 int_fast64_t
using namespace std;
int mark[1005][1005];
int dis[1005][1005];
int x1,ye,x2,y2;
int sx,sy,ex,ey;
int d[12][2] = {2,1,-2,-1,2,-1,-2,1,1,2,-1,-2,1,-2,-1,2,-2,2,2,2,2,-2,-2,-2};
struct node{
int x,y;
};
void bfs(int x,int y,int n,int m){
queue<node > q;
q.push({x,y});
memset(mark,0,sizeof(mark));
memset(dis,0,sizeof(dis));
mark[x][y] = 1;
dis[x][y] = 0;
while(!q.empty()){
node t = q.front();
q.pop();
for(int i=0;i<12;i++){
int dx = t.x + d[i][0];
int dy = t.y + d[i][1];
if(!mark[dx][dy] && dx >= 0&&dx <= n&&dy>=0&&dy <= m){
mark[dx][dy] = 1;
q.push({dx,dy});
dis[dx][dy] = dis[t.x][t.y] + 1;
if(dx == 1 && dy == 1){
cout << dis[dx][dy] << endl;
return ;
}
}
}
}
}
signed main(){
cin >> x1 >> ye;
cin >> x2 >> y2;
bfs(x1,ye,x1,ye);
bfs(x2,y2,x2,y2);
return 0;
}
```
by qhdx_zzd @ 2023-07-19 10:48:56
@[qhdx_zzd](/user/825829)
不是这样的的,你把这一行改成这样
```cpp
if(!mark[dx][dy] && dx >= 1&&dx <= 50&&dy>=1&&dy <= 50){
```
就能过了
by Brilliant11001 @ 2023-07-19 11:05:20
这个问题涉及从不同的袋子中选择字符串,将它们连接在一起形成目标字符串。以下是问题陈述和提供的示例输入的解释:
你开始时有一个空字符串S。此外,有N个袋子,每个包含一些字符串。第i个袋子包含Ai个字符串Si,1,Si,2,…,Si,Ai。
对于每个i,你可以选择并执行以下两种操作中的一种:
支付1日元,从第i个袋子中选择一个字符串,并将其连接到S的末尾。
什么也不做。
给定一个字符串T,找到使最终S等于T所需的最小金额。如果无法使S等于T,则输出-1。
示例输入 1
目标字符串:"abcde"
袋子数量:3
袋子1:3个字符串 - "ab", "abc", "abcd"
袋子2:4个字符串 - "f", "c", "cd", "bcde"
袋子3:2个字符串 - "e", "de"
示例输出 1
使S等于T("abcde")所需的最小金额为2日元。实现这一目标的步骤如下:
从袋子1选择"abc"并将其连接到S,使S="abc"。
对于袋子2,什么也不做。
从袋子3选择"de"并将其连接到S,使S="abcde"。
示例输入 2
目标字符串:"abcde"
袋子数量:3
袋子1:2个字符串 - "ab", "abc"
袋子2:3个字符串 - "f", "c", "bcde"
袋子3:1个字符串 - "e"
示例输出 2
无法使S等于T("abcde"),因此输出为-1。
示例输入 3
目标字符串:"aaabbbbcccc"
袋子数量:6
袋子1:2个字符串 - "aa", "aaa"
袋子2:2个字符串 - "dd", "ddd"
袋子3:2个字符串 - "ab", "aabb"
袋子4:4个字符串 - "bbaa", "bbbc", "bbb", "bbcc"
袋子5:2个字符串 - "cc", "bcc"
袋子6:3个字符串 - "ccc", "cccc", "ccccc"
示例输出 3
使S等于T("aaabbbbcccc")所需的最小金额为4日元。
by qhdx_zzd @ 2024-03-09 20:19:39