又重头开始刷kuangbin，有些题用了和以前不一样的思路解决。全部题解如下
点击每道题的标题即可跳转至VJ题目页面。
A-棋盘问题
棋子不能摆在相同行和相同列，所以我们可以依此枚举每一行，然后标记每一列是否走过，在此基础上进行DFS即可。
代码如下：
#include <iostream>
#include <cstring>
using namespace std;
int n,m,sum;
char mp[][];
int vis[] = {}; void dfs(int r,int k){
if(k == m){
sum++;
return ;
}
for(int i = r; i < n; i++){
for(int j = ; j < n; j++){
if(mp[i][j] == '#' && !vis[j]){
vis[j] = ;
dfs(i+,k+);
vis[j] = ;
}
}
}
} int main(){
while(cin>>n>>m && n > && m > ){
memset(vis, , sizeof vis);
sum = ;
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
cin>>mp[i][j];
}
}
dfs(,);
cout << sum << endl;
}
return ;
}
B-Dungeon Master
题意就是给你一个三维的迷宫，从S走到E，判断能否逃脱若能逃离则输出最短时间。
裸BFS/DFS，只是多了两个方向，向上走和向下走，我用的是BFS，代码如下：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std; int r,c,h;
char mp[][][];
bool vis[][][];
int sz,sx,sy,ez,ex,ey; int fx[][] = {{,,},{-,,},{,,},{,-,},{,,-},{,,}}; struct node{
int z,x,y,t;
}; bool check(int x,int y,int z){
if(mp[z][x][y] == '#' || vis[z][x][y] || z < || z >= h || x < || x >= r || y < || y >= c){
return false;
}
vis[z][x][y] = ;
return true;
} int bfs(){
memset(vis, false, sizeof vis);
queue<node> q;
q.push(node{sz,sx,sy,});
vis[sz][sx][sy] = ;
while(!q.empty()){
node now = q.front();
q.pop();
//cout << now.z << " " << now.x << " " << now.y << endl;
if(now.z == ez && now.x == ex && now.y == ey){
return now.t;
}
for(int i = ; i < ; i++){
int nx = now.x + fx[i][];
int ny = now.y + fx[i][];
int nz = now.z + fx[i][];
if(check(nx,ny,nz)){
q.push(node{nz,nx,ny,now.t+});
}
}
}
return -;
} int main(){
ios_base::sync_with_stdio();
while(cin >> h >> r >> c && r ){
for(int k = ; k < h; k++){
for(int i = ; i < r; i++){
for(int j = ; j < c; j++){
cin>>mp[k][i][j];
if(mp[k][i][j] == 'S'){
sz = k,sx = i,sy = j;
}
else if(mp[k][i][j] == 'E'){
ez = k,ex = i,ey = j;
}
}
}
}
int ret = bfs();
if(ret == -)
cout << "Trapped!" << endl;
else
cout << "Escaped in " << ret << " minute(s)." << endl; }
return ;
}
C-Catch That Cow
题意就是你现在在n位置处，牛在k位置处，你有下面三种走路方式，每次花费一分钟，牛不会动，问抓到牛的最小时间。
- 走到x+1位置处
- 走到x-1位置处
- 走到x*2位置处
BFS模拟即可，注意判断走到x*2时候，应该先判断x*2是否越界再判断vis[x*2]是否走过，可以用短路运算符&&实现，否则会造成RE，当然你也可以开成两倍的 数组空间来避免这种错误，但我还是推荐使用前者方式。
代码如下：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std; int n,k;
bool vis[]; struct node{
int s,t;
}; int bfs(){
memset(vis,,sizeof vis);
queue<node> q;
q.push(node{n,});
vis[n] = ;
while(!q.empty()){
node now = q.front();
q.pop();
if(now.s == k)
return now.t;
if(now.s- >= && !vis[now.s-]){
vis[now.s-] = ;
q.push(node{now.s-,now.t+});
}
if(now.s+ <= && !vis[now.s+]){
vis[now.s+] = ;
q.push(node{now.s+,now.t+});
}
if(now.s* <= && !vis[now.s*]){
vis[now.s*] = ;
q.push(node{now.s*,now.t+});
}
}
return ;
} int main(){
ios_base::sync_with_stdio();
while(cin>>n>>k){
cout << bfs() << endl;
}
return ;
}
D-Fliptile
玩过关灯游戏理解这个题就很简单，n*m的矩阵，0代表灯关，1代表灯开，然后可以反转某个灯的状态，但是这个灯周围四个方向的灯也会反转，然后问如何吧所有灯全关掉，若是不可能则输出IMPOSSIBLE，若是有多种情况请输出字典序最小的那个操作矩阵。
思路就是枚举，如何枚举，首先我们可以枚举第一层的每种操作可能，若是上一层有灯没关，这层的相应位置则必须反转，这样只要判断最下面一层的灯是否全关了即可。
那么我们需要对第一层枚举多少种状态呢？答案是2^m种，为什么呢，因为每层有m个灯，每种灯两个状态，所以就是2^m种操作方式，每种操作方式也就刚好对应了0——2^m-1中数的二进制，
例如对于样例，需要枚举0——15
0 = 0000
1 = 0001
……
15 = 1111
二进制刚好就是第一层的操作方式，然后我们从第二层开始，判断上一层是否还有状态为灯开的灯，有则操作当前位置，再判断最后一层是否全为灯关。
至于字典序处理，我们只需要数操作矩阵1的个数，找最小值即可，你可能会问相等的情况呢，因为我们是按0->2^m-1，所以若是前面的1个数和后面1个数相等，字典序一定是前面的更小，所以无需考虑。
代码如下：
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <cmath>
#include <climits>
using namespace std; int n,m;
int mp[][],fp[][],vis[][];
int fx[][] = {{,},{-,},{,},{,-}}; void change(int i,int j){
fp[i][j] ^= ;
for(int k = ; k < ; k++){
int ni = i + fx[k][];
int nj = j + fx[k][];
if(ni >= && nj >= && ni < n && nj < m){
fp[ni][nj] ^= ;
}
}
} int dfs(int k){
memcpy(fp, mp, sizeof fp);
memset(vis, , sizeof vis);
int tot = m-,res = ;
while(k || tot>=){
int t = k%;
vis[][tot] = t;
res+=t;
if(t == )
change(,tot);
tot--;
k /= ;
}
//cout << setw(3) << setfill('0') << *fp[0] << endl;
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
if(fp[i-][j] == ){
vis[i][j] = ;
res++;
change(i,j);
}
}
}
for(int j = ; j < m; j++){
if(fp[n-][j] == )
return **;
}
return res;
} int main(){
ios_base::sync_with_stdio(),cin.tie(),cout.tie();
while(cin>>n>>m){
int ans[][];
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
cin>>mp[i][j];
}
}
int num = pow(,m),minn = INT_MAX;
for(int i = ; i < num; i++){
int ret = dfs(i);
if(ret < minn){
memcpy(ans, vis, sizeof vis);
minn = ret;
}
}
if(minn == **)
cout << "IMPOSSIBLE" << endl;
else{
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
if(j == )
cout << ans[i][j];
else
cout << " " << ans[i][j];
}
cout << endl;
}
}
}
return ;
}
E-Find The Multiple
题意就是给你一个数n，然后让你找到一个只由1和0构成的数x，使得x是n的倍数。
BFS遍历即可，所有数组都在long long范围内有解，其实甚至都不需要BFS，直接依此枚举即可。
代码如下：
#include <iostream>
#include <cstring>
#include <queue>
#include <string>
using namespace std; int n; long long bfs(){
queue<long long> q;
q.push();
while(!q.empty()){
long long x = q.front();
q.pop();
if(x % n == ){
return x;
}
q.push(x*);
q.push(x*+);
}
return ;
} int main(){
while(cin>>n && n){
cout << bfs() << endl;
}
return ;
}
F-Prime Path
题意就是给你两个数p1，p2，两个数都是四位数且都是素数，现在要把p1变成p2，规则是每次只能变换某一位上的数，且保证变换过程中的数也是素数。求最小变换次数。
还是BFS撒，从最高位开始变换，枚举所有素数的变换情况直至找到p2位置，这题麻烦的是变一位的数。
代码如下：
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std; int a,b;
int sum = ;
bool vis[]; struct node{
int x,s;
}; int change(int k,int i,int j){
return k - (int(k/pow(,-i))%)*pow(,-i) + j*pow(,-i);
} bool isprime(int n){
if(n== || n==)
return true;
if(n% != && n% != )
return false;
float n_sqrt = floor(sqrt((float)n));
for(int i = ; i <= n_sqrt; i += )
if(n%(i) == | n%(i+) == )
return false;
return true;
} int bfs(int k){
vis[k] = ;
queue<node> q;
q.push(node{k,});
while(!q.empty()){
node now = q.front();
//cout << now.x << endl;
q.pop();
if(now.x == b)
return now.s;
for(int i = ; i < ; i++){
for(int j = ; j >= ; j--){
if(i == && j == ) break;
int t = change(now.x,i,j);
if(isprime(t) && !vis[t]){
vis[t] = ;
q.push(node{t,now.s+});
}
}
}
}
return ;
} int main(){
int t;
cin>>t;
while(t--){
memset(vis, , sizeof vis);
cin>>a>>b;
sum = bfs(a);
cout << sum << endl;
}
return ;
}
G-Shuffle'm Up
给你两个字符串长度都为n的字符串s1、s2，然后可以结合成题目图中那种形状，s2和s1交叉且s2的最下面一块在结合后的形状中还是最下面一块，s1又变成结合后的串的前n个字符，s2变成后n个字符，判断能否得到想要的字符串并询问最小变换次数。
主要考字符串处理，代码如下：
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std; string s1,s2,es;
int n;
map<string,int> vis; string fun(string a,string b){
string s = "";
for(int i = ; i < n; i++){
s += b[i];
s += a[i];
}
return s;
} int bfs(){
int tot = ;
while(){
tot ++;
string ss = fun(s1,s2);
//cout << ss << endl;
if(ss == es)
return tot;
if(!vis[ss])
vis[ss] = ;
else
break;
s1 = ss.substr(,n);
s2 = ss.substr(n,n);
}
return -;
} int main(){
int t;
cin>>t;
for(int tt = ; tt <= t; tt++){
cin>>n>>s1>>s2>>es;
cout << tt << ' ' << bfs() << endl;
}
return ;
}
H-Pots
题意：有两个壶，容量分别为A，B，现在想要C（C ≤ max(a,b)）容量的水，然后可以相互倒水（只能倒到另一壶满或者本壶倒完为止），倒空本壶，装满本壶。问操作次数（SPJ，不需要最小操作 次数）并且应该如何操作。
因为有SPJ存在，所以直接BFS就行了，主要麻烦的是如何存储每次的操作。我是用一个vector<pair<char,int>>来实现，这样会消耗很大的空间，但题目空间很充裕，所以这个做法没有问题。
代码如下：
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
using namespace std; int a,b,c;
bool vis[][]; struct node{
int a,b;
vector< pair<char,int> > v;
}; void print(node n){
cout << n.v.size() << endl;
for(vector< pair<char,int> >::iterator it = n.v.begin(); it != n.v.end(); it++){
if(it->first == 'f')
cout << "FILL(" << it->second << ")" << endl;
else if(it->first == 'd')
cout << "DROP(" << it->second << ")" << endl;
else if(it->first == 'p')
cout << "POUR(" << it->second << ',' << (it->second == ?:) << ")" << endl;
}
return ;
} void bfs(){
memset(vis, , sizeof vis);
queue<node> q;
q.push(node{,});
vis[a][b] = ;
while(!q.empty()){
node now = q.front(),nt;
//cout << now.a << ' ' << now.b << endl;
q.pop();
if(now.a == c || now.b == c){
print(now);
return ;
}
if(now.a != && !vis[][now.b]){
vis[][now.b] = ;
nt = now;
nt.a = ;
nt.v.push_back(make_pair('d',));
q.push(nt);
}
if(now.b != && !vis[][now.a]){
vis[now.a][] = ;
nt = now;
nt.b = ;
nt.v.push_back(make_pair('d',));
q.push(nt);
}
if(now.a != a && !vis[a][now.b]){
vis[a][now.b] = ;
nt = now;
nt.a = a;
nt.v.push_back(make_pair('f',));
q.push(nt);
}
if(now.b != b && !vis[b][now.a]){
vis[now.a][b] = ;
nt = now;
nt.b = b;
nt.v.push_back(make_pair('f',));
q.push(nt);
}
if(now.a > && now.b != b){
int tb = now.b+now.a >= b?b:now.b+now.a;
int ta = b-now.b >= now.a?:now.a-b+now.b;
if(!vis[ta][tb]){
vis[ta][tb] = ;
nt = now;
nt.a = ta;
nt.b = tb;
nt.v.push_back(make_pair('p',));
q.push(nt);
}
}
if(now.a != a && now.b > ){
int ta = now.a+now.b >= a?a:now.a+now.b;
int tb = a-now.a >= now.b?:now.b-a+now.a;
if(!vis[ta][tb]){
vis[ta][tb] = ;
nt = now;
nt.a = ta;
nt.b = tb;
nt.v.push_back(make_pair('p',));
q.push(nt);
}
}
}
cout << "impossible" << endl;
return ;
} int main(){
while(cin>>a>>b>>c){
bfs();
}
return ;
}
I-Fire!
题意就是人在J位置处，火在F位置处，不一定只有一堆火，火每分钟会向四周蔓延，人每分钟可以走一格，问能否逃出以及最小逃跑时间。
做了一遍再对比了一下以前的代码，发现区别还是很大的，以前是人每走一格就去BFS使得火蔓延一次，现在的做法是BFS人到达每个出口的时间，再BFS火到达每个出口的时间，再判断大小也就是判断人能否在火之前到达出口。
两份代码如下：
BEFORE（乱七八糟的宏定义比较多= =）：
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <bitset>
#include <ctime>
#include <fstream>
#include <limits.h>
#include <numeric> using namespace std; #define F first
#define S second
#define mian main
#define ture true #define MAXN 1000000+5
#define MOD 1000000007
#define PI (acos(-1.0))
#define EPS 1e-6
#define MMT(s) memset(s, 0, sizeof s)
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef stringstream sstm;
const int INF = 0x3f3f3f3f; int n,m,t,jx,jy;
char mp[][];
int vis[][];
int fx[][] = {,,-,,,-,,};
vector< pair<int,int> >q; void init(){
MMT(mp);
fill(vis[],vis[]+*,);
q.clear();
} bool check(int x,int y){
if(x < || x >= n || y < || y >= m || mp[x][y] == '#' || vis[x][y])
return false;
return true;
} int bfs(){
queue< pair<int,int> >p;
queue< pair<int,int> >pf;
p.push(make_pair(jx,jy));
int step = ;
for(int i = , len = q.size(); i < len; i++){
vis[q[i].F][q[i].S] = ;
pf.push(q[i]);
}
vis[jx][jy] = ;
while(!p.empty()){
pair<int,int>nx = p.front(); if(nx.F == || nx.F == n- || nx.S == || nx.S == m-)
return vis[nx.F][nx.S]; if(vis[nx.F][nx.S] > step)
step++;
if(vis[nx.F][nx.S] == step){
while(!pf.empty()){
pair<int,int>nf = pf.front();
if(vis[nf.F][nf.S] > step)
break;
pf.pop();
for(int i = ; i < ; i++){
int nxx = nf.F + fx[i][];
int nxy = nf.S + fx[i][];
if(check(nxx,nxy)){
vis[nxx][nxy] = vis[nf.F][nf.S] + ;
pf.push(make_pair(nxx,nxy));
}
}
}
}
p.pop();
for(int i = ; i < ; i++){
int nxx = nx.F + fx[i][];
int nxy = nx.S + fx[i][];
if(check(nxx,nxy)){
vis[nxx][nxy] = vis[nx.F][nx.S] + ;
p.push(make_pair(nxx,nxy));
}
}
}
return -;
} int main(){
ios_base::sync_with_stdio(false);
cout.tie();
cin.tie();
cin>>t;
while(t--){
init();
cin>>n>>m;
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
cin>>mp[i][j];
if(mp[i][j] == 'J'){
jx = i, jy = j;
}
if(mp[i][j] == 'F'){
q.push_back(make_pair(i,j));
}
}
}
int ret = bfs();
if(ret > )
cout << ret << endl;
else
cout << "IMPOSSIBLE" << endl; }
return ;
}
NOW：
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <climits>
#include <queue>
using namespace std; int n,m;
char mp[][];
int dis[][];
int fdis[][];
bool vis[][];
int px,py;
int fx[][] = {{,},{-,},{,-},{,}};
struct node{
int x,y;
}; queue<node> q[]; bool pass1(int x,int y){
if(x < || y < || x >= n || y >= m || mp[x][y] != '.' || dis[x][y])
return false;
return true;
} bool pass2(int x,int y){
if(x < || y < || x >= n || y >= m || mp[x][y] == '#' || fdis[x][y])
return false;
return true;
} void bfs(){
while(!q[].empty()){
node now = q[].front();
q[].pop();
for(int i = ; i < ; i++){
int nx = now.x + fx[i][];
int ny = now.y + fx[i][];
if(pass1(nx,ny)){
q[].push(node{nx,ny});
dis[nx][ny] = dis[now.x][now.y]+;
}
}
} while(!q[].empty()){
node now = q[].front();
q[].pop();
for(int i = ; i < ; i++){
int nx = now.x + fx[i][];
int ny = now.y + fx[i][];
if(pass2(nx,ny)){
q[].push(node{nx,ny});
fdis[nx][ny] = fdis[now.x][now.y]+;
}
}
}
} int check(){
int ans = INT_MAX;
for(int j = ; j < m; j++){
if(dis[][j] > && (fdis[][j] > dis[][j] || fdis[][j] == ))
ans = min(ans,dis[][j]);
if(dis[n-][j] > && (fdis[n-][j] > dis[n-][j] || fdis[n-][j] == ))
ans = min(ans,dis[n-][j]);
}
for(int j = ; j < n; j++){
if(dis[j][] > && (fdis[j][] > dis[j][] || fdis[j][] == ))
ans = min(ans,dis[j][]);
if(dis[j][m-] > && (fdis[j][m-] > dis[j][m-] || fdis[j][m-] == ))
ans = min(ans,dis[j][m-]);
}
if(ans == INT_MAX)
return -;
else
return ans;
} void init(){
while(!q[].empty()) q[].pop();
while(!q[].empty()) q[].pop();
memset(dis, , sizeof dis);
memset(fdis, , sizeof fdis);
return ;
} int main(){
int t;
cin>>t;
while(t--){
init();
cin>>n>>m;
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
cin>>mp[i][j];
if(mp[i][j] == 'J')
q[].push(node{i,j}),dis[i][j] = ;
if(mp[i][j] == 'F')
q[].push(node{i,j}),fdis[i][j] = ;
}
}
bfs();
int ret = check();
if(ret == -)
cout << "IMPOSSIBLE" << endl;
else
cout << ret << endl;
}
return ;
}
J-迷宫问题
这个我以前写过一篇博客https://www.cnblogs.com/xenny/p/9473555.html
然后再贴一下现在的代码吧:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std; char mp[][];
bool vis[][];
int fx[][] = {{,},{-,},{,},{,-}};
vector< pair<int,int> > ans(,make_pair(,));
bool pass(int x,int y){
if(x < || y < || x >= || y >= || vis[x][y] || mp[x][y] == '')
return false;
return true;
} void print(vector< pair<int,int> > v){
for(vector< pair<int,int> >::iterator it = v.begin(); it != v.end(); it++){
cout << '(' << it->first << ", " << it->second << ')' << endl;
}
} void dfs(int x,int y,vector< pair<int,int> > v){
if(x == && y == ){
if(ans.size() == || v.size() < ans.size())
ans = v;
return ;
}
for(int i = ; i < ; i++){
int nx = x + fx[i][];
int ny = y + fx[i][];
if(pass(nx,ny)){
vis[nx][ny] = ;
v.push_back(make_pair(nx,ny));
dfs(nx,ny,v);
v.erase(--v.end());
vis[nx][ny] = ;
}
}
} int main(){
memset(vis, , sizeof vis);
vis[][] = ;
for(int i = ; i < ; i++){
for(int j = ; j < ; j++){
cin>>mp[i][j];
}
}
dfs(,,ans);
print(ans);
return ;
}
感觉现在写的比以前的还是清晰明了了很多= =
K-Oil Deposits
很多人的搜索入门题都是这个题目吧，很经典，就是问有几块油田，一块油田的8个方向内有油田就看为连在一起。
把遍历过的油田记为*号，都可以把vis数组都省略掉。
代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std; int n,m;
char mp[][];
int fx[][] = {{,},{-,},{,},{,-},{,},{,-},{-,},{-,-}}; bool pass(int x,int y){
if(x < || y < || x >= n || y >= m || mp[x][y] == '*')
return false;
return true;
} void dfs(int x,int y){
for(int i = ; i < ; i++){
int nx = x + fx[i][];
int ny = y + fx[i][];
if(pass(nx,ny)){
mp[nx][ny] = '*';
dfs(nx,ny);
}
}
} int main(){
while(cin>>n>>m && n){
int sum = ;
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
cin>>mp[i][j];
}
}
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
if(mp[i][j] == '@'){
sum++;
dfs(i,j);
}
}
}
cout << sum << endl;
}
return ;
}
L-非常可乐
和Pots那个题类似，也是枚举每种状态，但是其实在搜索还可以加上剪枝，例如s为奇数直接输出NO，然后本题还有数学做法，可以自行百度，我不再给出。
代码如下：
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; int s,n,m;
bool vis[][][];
struct node{
int s,n,m,t;
}; bool check(node n){
if((n.s > && n.n > && n.s == n.n && n.s + n.n == s) || \
(n.s > && n.m > && n.s == n.m && n.s + n.m == s) || \
(n.m > && n.n > && n.m == n.n && n.m + n.n == s))
return true;
return false;
} int bfs(){
memset(vis, , sizeof vis);
queue<node> q;
q.push(node{s,,,});
vis[s][][] = ;
while(!q.empty()){
node now = q.front();
q.pop();
if(check(now)){
return now.t;
}
node nt = now;
nt.s = now.s - (n-now.n) <= ? : now.s - (n-now.n);
nt.n = now.n + now.s >= n ? n : now.n + now.s;
if(!vis[nt.s][nt.n][nt.m]){
vis[nt.s][nt.n][nt.m] = ;
nt.t = now.t+;
q.push(nt);
}
nt = now;
nt.s = now.s - (m-now.m) <= ? : now.s - (m-now.m);
nt.m = now.m + now.s >= m ? m : now.m + now.s;
if(!vis[nt.s][nt.n][nt.m]){
vis[nt.s][nt.n][nt.m] = ;
nt.t = now.t+;
q.push(nt);
}
nt = now;
nt.n = now.n - (s-now.s) <= ? : now.n - (s-now.s);
nt.s = now.n + now.s >= s ? s : now.n + now.s;
if(!vis[nt.s][nt.n][nt.m]){
vis[nt.s][nt.n][nt.m] = ;
nt.t = now.t+;
q.push(nt);
}
nt = now;
nt.m = now.m - (s-now.s) <= ? : now.m - (s-now.s);
nt.s = now.m + now.s >= s ? s : now.m + now.s;
if(!vis[nt.s][nt.n][nt.m]){
vis[nt.s][nt.n][nt.m] = ;
nt.t = now.t+;
q.push(nt);
}
nt = now;
nt.n = now.n - (m-now.m) <= ? : now.n - (m-now.m);
nt.m = now.m + now.n >= m ? m : now.m + now.n;
if(!vis[nt.s][nt.n][nt.m]){
vis[nt.s][nt.n][nt.m] = ;
nt.t = now.t+;
q.push(nt);
}
nt = now;
nt.m = now.m - (n-now.n) <= ? : now.m - (n-now.n);
nt.n = now.n + now.m >= n ? n : now.m + now.n;
if(!vis[nt.s][nt.n][nt.m]){
vis[nt.s][nt.n][nt.m] = ;
nt.t = now.t+;
q.push(nt);
}
}
return -;
} int main(){
while(cin>>s>>n>>m && s){
int ret = bfs();
if(ret == -)
cout << "NO" << endl;
else
cout << ret << endl;
}
return ;
}
M-Find a way
这个题我也写过博客，还是我的第一篇题解博客。
地址链接：https://www.cnblogs.com/xenny/p/9361825.html
然后这是现在写的代码：
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std; char mp[][];
int vis[][][];
int fx[][] = {,,,-,-,,,};
int n,m,yx,yy,mx,my;
struct node{
int x,y;
}; const int inf = ; bool check(int x,int y,int z){
if(vis[x][y][z] != inf || x < || x >= n || y < || y >= m || mp[x][y] == '#')
return false;
return true;
} void bfs(int x,int y,int z){
vis[x][y][z] = ;
queue<node>q;
q.push(node{x,y});
while(!q.empty()){
node now = q.front();
q.pop();
for(int i = ; i < ; i++){
int nx = now.x + fx[i][];
int ny = now.y + fx[i][];
if(check(nx,ny,z)){
vis[nx][ny][z] = vis[now.x][now.y][z] + ;
q.push(node{nx,ny});
}
}
}
} int main(){
while(cin>>n>>m){
fill(vis[][], vis[][]+**, inf);
vector< pair<int,int> > v;
for(int i = ; i < n; i++){
for(int j = ; j < m; j++){
cin>>mp[i][j];
if(mp[i][j] == 'Y')
yx = i,yy = j;
if(mp[i][j] == 'M')
mx = i,my = j;
if(mp[i][j] == '@')
v.push_back(make_pair(i,j));
}
}
bfs(yx,yy,);
bfs(mx,my,);
int ans = INT_MAX;
for(vector< pair<int,int> >::iterator it = v.begin(); it != v.end(); it++)
ans = min(ans,vis[it->first][it->second][] + vis[it->first][it->second][]);
cout << ans* << endl;
} return ;
}
看了以前的博客和现在的，区别还是挺大的，各位也可以尝试用多种方法解决一道题。关于kuangbin专题一的所有题目到此就完了，又不懂的地方可以在评论区留言，同时欢迎指正上面代码的错误。