1114. 棋盘问题 - AcWing题库

题意

​ 在一个给定形状的棋盘中，摆放棋子，要求同一行和同一列最多只能有一个棋子。

题解

​ 这实际上就是 $n$ 皇后的改版，直接使用 $DFS$ 搜就行了。

#include
#include
using namespace std;
const int N=10;
int n,k,ans;
char g[N][N];
bool col[N];
void dfs(int u,int cnt){
    if(cnt==k){
        ans++;
        return;
    }
    if(u==n)return;
    dfs(u+1,cnt);
    for(int i=0;i<n;i++){
        if(g[u][i]=='#'&&!col[i]){
            col[i]=true;
            dfs(u+1,cnt+1);
            col[i]=false;
        }
    }
}
int main(){
    while(cin>>n>>k){
        memset(col,false,sizeof col);
        if(n==-1&&k==-1)break;
        ans=0;
        for(int i=0;i<n;i++)cin>>g[i];
        dfs(0,0);
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

1096. 地牢大师 - AcWing题库

题意

​ 在一个三维地牢中，给定每一层的地图，并标注起点和终点，判断能否从起点到达终点，能就输出移动的最短路径长度。

题解

​ 二维走迷宫的拓展，在使用 $BFS$ 的时候加多一维就行了。

#include
#include
#include
using namespace std;
const int N=110;
int l,r,c;
int st[N][N][N];
char g[N][N][N];
struct point{
    int z,x,y;
}S,E;
int dx[]={1,0,0,-1,0,0};
int dy[]={0,1,0,0,-1,0};
int dz[]={0,0,1,0,0,-1};
void bfs(){
    queue<point>q;
    q.push(S);
    st[S.z][S.x][S.y]=0;
    while(q.size()){
        auto u=q.front();
        q.pop();
        for(int i=0;i<6;i++){
            int x=u.x+dx[i];
            int y=u.y+dy[i];
            int z=u.z+dz[i];
            if(x&&x<=r&&y&&y<=c&&z&&z<=l&&st[z][x][y]==-1&&(g[z][x][y]=='.'||g[z][x][y]=='E')){
                q.push({z,x,y});
                st[z][x][y]=st[u.z][u.x][u.y]+1;
            }
        }
    }
}
int main(){
    while(cin>>l>>r>>c&&(l||r||c)){
        memset(st,-1,sizeof st);
        for(int i=1;i<=l;i++)
            for(int j=1;j<=r;j++)
                for(int k=1;k<=c;k++){
                    cin>>g[i][j][k];
                    if(g[i][j][k]=='S')S={i,j,k};
                    if(g[i][j][k]=='E')E={i,j,k};
                }
        bfs();
        if(st[E.z][E.x][E.y]==-1)puts("Trapped!");
        else cout<<"Escaped in "<<st[E.z][E.x][E.y]<<" minute(s)."<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

1100. 抓住那头牛 - AcWing题库

题意

​ 农夫和牛在一个一维数轴上，农夫在点 $N$，牛在点 $K$，农夫有两种移动方式

• 从 $X$ 移动到 $X-1$ 或 $X+1$，每次移动花费一分钟

• 从 $X$ 移动到 $2\times X$，每次移动花费一分钟

求农夫最少要多少分钟能到达牛的位置

题解

​ 将农夫的每次有三种移动的可能，每次都将这三种可能放入队列中进行 $BFS$。贪心得出，每次第一次入队的点一定是到达该点的最短距离。同时进行剪枝，要是当前的移动超过了数轴给出的范围就直接舍弃。

#include
#include
using namespace std;
const int N=1e5+10;
int n,m;
int dist[N];
bool st[N];
int bfs(){
    queue<int>q;
    dist[n]=0;
    q.push(n);
    while(q.size()){
        int t=q.front();q.pop();
        if(t==m)return dist[t];
        
        int a=t-1,b=t+1,c=2*t;
        if(a>=0&&a<=N-10&&!st[a]){
            dist[a]=dist[t]+1;
            q.push(a);
            st[a]=true;
        }
        if(b>=0&&b<=N-10&&!st[b]){
            dist[b]=dist[t]+1;
            q.push(b);
            st[b]=true;
        }
        if(c>=0&&c<=N-10&&!st[c]){
            dist[c]=dist[t]+1;
            q.push(c);
            st[c]=true;
        }
    }
}
int main(){
    cin>>n>>m;
    if(n>m){
        cout<<n-m<<endl;
    }else{
        int ans=bfs();
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

4218. 翻转 - AcWing题库

题意

​ 给定一个 $01$ 矩阵，存在操作，任意选择一个位置，并将当前位置元素以及上下左右的元素进行翻转（他如），求怎样操作能将整个数组转换为 $0$，要是不存在这种操作就输出 “IMPOSSIBLE”。

题解

​ 这个可以用状压解决，首先有一个结论，就是只有第一行是需要分情况的，要是第一行已经操作完，后续的所有操作就已经确定了。

• 证明：因为当第一行确定的时候，再想要改变上一行某元素的情况，只能操作该元素的下方向元素。

​ 于是只需要枚举第一行的操作情况就行了。

#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int N=20;
int n,m;
int g[N][N],back[N][N];
int tmp[N][N],ans[N][N];
void turn(int x,int y){
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    g[x][y]^=1;
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx&&nx<=n&&ny&&ny<=m)
            g[nx][ny]^=1;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    memcpy(back,g,sizeof g);
    int st=1<<m;
    
    int res=inf;
    for(int i=0;i<st;i++){
        memcpy(g,back,sizeof back);
        memset(tmp,0,sizeof tmp);
        int cnt=0;
        for(int j=1;j<=m;j++){
            if(i>>(j-1)&1){
                turn(1,j);
                cnt++;
                tmp[1][j]=1;
            }
        }
        
        for(int j=2;j<=n;j++){
            for(int k=1;k<=m;k++){
                if(g[j-1][k]){
                    turn(j,k);
                    cnt++;
                    tmp[j][k]=1;
                }
            }
        }
        
        bool flag=false;
        for(int j=1;j<=m;j++){
            if(g[n][j]){
                flag=true;
                break;
            }
        }
        if(!flag){
            if(res>cnt){
                res=cnt;
                memcpy(ans,tmp,sizeof tmp);
            }
        }
    }
    if(res==inf){
        puts("IMPOSSIBLE");
    }else{
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout<<ans[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

4219. 找倍数 - AcWing题库

题意

​ 给定一个整数 $n$，要求找出一个 $n$ 的非 $0$ 倍数 $m$，其中要求 $m$ 只能由 $01$ 构成。

题解

​ 直接暴力枚举每一个由 $01$ 组成的数字，并判断能否将 $n$ 整除。这样真是可行的，虽然不知道怎么去证明，但是打表出来显示在数据范围内的数字都可以在 $longlong$ 范围内被找到。

#include
#include
using namespace std;
int n;
int main(){
    while(cin>>n,n){
        queue<long long>q;
        q.push(1);
        while(q.size()){
            auto t=q.front();
            q.pop();
            if(t%n==0){
                cout<<t<<endl;
                break;
            }
            q.push(t*10);
            q.push(t*10+1);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4220. 质数路径 - AcWing题库

题意

​ 给定两个四位数的质数 $A,B$，每次可以改 $A$ 的一位数字，每次修改后必须还是质数，问将 $A$ 变为 $B$ 的最小步数是多少，无解则输出 “Impossible”。（实际测试不存在无解情况）

题解

​ 直接 $BFS$ 操作每一位数字的每一种情况就行了。

#include
#include
#include
#include
using namespace std;
const int N = 10010;
int primes[N],cnt;
bool st[N];
void get_primes(int n){
    for (int i=2;i<=n;i++){
        if(!st[i])primes[cnt++]=i;
        for (int j=0;primes[j]<=n/i;j++){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int _,dist[N];
int dx[]={1000,100,10,1};
void solve(){
    memset(dist,-1,sizeof dist);
    int a,b,v[4];
    queue<int>q;
    cin>>a>>b;
    q.push(a),dist[a]=0;
    while(q.size()){
        auto t=q.front();q.pop();
        if(t==b)break;
        v[3]=t%10,v[2]=t%100/10,v[1]=t%1000/100,v[0]=t/1000;
        for(int i=0;i<10;i++){
            for(int j=0;j<4;j++){
                if(!i&&!j)continue;
                int k=t+dx[j]*(i-v[j]);
                if(!st[k]&&dist[k]==-1){
                    q.push(k);
                    dist[k]=dist[t]+1;
                }
            }
        }
    }
    if(dist[b]==-1)puts("Impossible");
    else cout<<dist[b]<<endl;
}
int main(){
    get_primes(N-10);
    cin>>_;while(_--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

4221. 洗牌 - AcWing题库

题意

​ 给定两叠张数为 $n$ 的纸牌 $a,b$，存在洗牌操作：依从 $b$ 和 $a$ 的顶部抽一张牌组成一叠新的张数为 $2\times n$ 的纸牌，然后下半部分是新的 $b$ 上半部分是新的 $a$，问能否在任意次操作后将纸牌变为指定的堆叠顺序，要是不存在输出 “-1”。

题解

​ 该题主要是判断何时判断是不能构成的，当当前洗出的牌之前出现过就可以判定为是形成回路了，这样就可以判定不存在解了，其余的就再次洗牌就行了。

#include
#include
using namespace std;
int _,n,o=0;
string change(string a,string b){
	string res;
	for(int i=0;i<(int)a.size();i++){
		res+=b[i],res+=a[i];
	}
	return res;
}
void solve(){
    cout<<++o<<" ";
	string a,b,s;
	cin>>n>>a>>b>>s;
	int ans=1;
	map<string,int>mp;
	string t=change(a,b);
	while(true){
		if(mp[t]!=0){
			puts("-1");
			return ;
		}else if(t==s){
			cout<<ans<<endl;
			return ;
		}else{
			mp[t]=1;
		}
		ans++;
		t=change(t.substr(0,n),t.substr(n,n));
	}
}
int main(){
    cin>>_;while(_--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

4222. 罐子 - AcWing题库

题意

​ 给定两个容积为 $a$ 和 $b$ 的罐子，存在种操作

• 将罐子装满
• 将罐子倒空
• 将一个罐子的水倒向另一个罐子，直到罐子为空或另一个罐子满。

问至少多少次操作后可以得出给定的容积，无解则输出 “impossible”。

题解

​ 可以将三种操细化为 $6$ 种操作，分别是清空 $a$ 罐子，清空 $b$ 罐子，加满 $a$ 罐子，加满 $b$ 罐子，将 $a$ 罐子的水倒向 $b$ 罐子，将 $b$ 罐子的水倒向 $a$ 罐子。然后按照每次按照这 $6$ 种方向进行移动。

#include 
#include 
#include 
using namespace std;
const int N=110;
int a,b,c;
struct Point{
    int x,y;
    string str;
};
string op[6]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int dist[N][N];
Point bfs(){
    memset(dist,-1,sizeof dist);
    queue<Point>q;
    q.push({0,0,""});
    dist[0][0]=0;
    while(q.size()){
        Point t=q.front();q.pop();
        if(t.x==c||t.y==c)
            return t;
        int dx[6]={a-t.x,0    ,-t.x,0   ,-1*min(t.x,b-t.y),min(a-t.x,t.y)};
        int dy[6]={0    ,b-t.y,0   ,-t.y,min(t.x,b-t.y) ,-1*min(a-t.x,t.y)};
        for(int i=0;i<6;i++){
            int x=t.x+dx[i];
            int y=t.y+dy[i];
            if(dist[x][y]==-1){
                dist[x][y]=dist[t.x][t.y]+1;
                q.push({x,y,t.str+(char)(i+'0')});
            }
        }
    }
    puts("impossible");
    Point fa={-1,-1,""};
    return fa;
}
int main(){
    cin>>a>>b>>c;
    Point ans=bfs();
    if(ans.x!=-1)cout<<dist[ans.x][ans.y]<<endl;
    for(int i=0;i<ans.str.size();i++){
        cout<<op[ans.str[i]-'0']<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

4223. 点火游戏 - AcWing题库

题意

​ 给定一个 $n\times m$ 的矩阵，其中一部分是草地一部分是空地，草地可以被燃烧，但是空地不行，当一块草地当前是燃烧的时候在下一个时间其上下左右的草地也会被燃烧。

初始可以选择两个位置放火，求烧完所有草的最小时间。

题解

​ 可以直接暴力枚举每两个点进行放火，然后判断每次的时间。在这一题中暴力枚举的复杂度是够的，但是在数据量大的时候有个想法就是随机使用一个点，再跑出这个点的最远距离点，这可能是一个剪枝的方法，（或者是另一个思路？）。

#include
#include
#include
#include
using namespace std;
#define x first
#define y second
typedef pair<int,int>pii;
const int N=20;
const int inf=0x3f3f3f3f;
int _,n,m,dist[N][N],o=0;
char g[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
vector<pii>p;
int bfs(pii a,pii b){
	memset(dist,-1,sizeof dist);
	queue<pii>q;
	q.push(a);
	if(a!=b)q.push(b);
	dist[a.x][a.y]=dist[b.x][b.y]=0;
	int cnt=0,tt=0;
	while(q.size()){
		auto t=q.front();q.pop();
		for(int i=0;i<4;i++){
			int x=t.x+dx[i];
			int y=t.y+dy[i];
			if(x&&y&&x<=n&&y<=m&&g[x][y]=='#'&&dist[x][y]==-1){
				dist[x][y]=dist[t.x][t.y]+1;
				tt=max(tt,dist[x][y]);
				q.push({x,y});
			}
		}
		cnt++;
	}
	if(cnt==(int)p.size())return tt;
	else return -1;
}
void solve(){
	p.clear();
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='#')p.push_back({i,j});
		}
	int ans=inf;
	if(p.empty()){
		ans=-1;
	}else{
		for(int i=0;i<(int)p.size();i++){
			for(int j=i;j<(int)p.size();j++){
				int tmp=bfs(p[i],p[j]);
				if(tmp!=-1)ans=min(ans,tmp);
			}
		}
	}
	if(ans==inf)ans=-1;
	cout<<"Case "<<++o<<": "<<ans<<endl;
}
int main(){
    cin>>_;while(_--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

4224. 起火迷宫 - AcWing题库

题意

​ 在一个 $n\times m$ 的二维迷宫中，乔困在其中，迷宫中还有一些空地已经着火，着火的空地每时间会向上下左右延伸，求乔能否逃出迷宫（在迷宫的边缘的下一个单位时间就能逃出），若逃不出去则输出 “IMPOSSIBLE”。

题解

​ 注意着火点可能不止一处，还有初始就在迷宫边缘的情况。

​ 进行两次 $BFS$ 进行比较，只要乔能在火之前到达就有解。

#include
#include
#include
#include
using namespace std;
#define x first
#define y second
typedef pair<int,int>pii;
const int N=1010;
const int inf=0x3f3f3f3f;
int _,n,m,d1[N][N],d2[N][N];
char g[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
void solve(){
	memset(d1,0x3f,sizeof d1);
	memset(d2,0x3f,sizeof d2);
	cin>>n>>m;
	queue<pii>a,b;
	int s0,t0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='F')a.push({i,j}),d1[i][j]=0;
			if(g[i][j]=='J')b.push({i,j}),d2[i][j]=0,s0=i,t0=j;
		}
	}
	if(s0==1||s0==n||t0==1||t0==m){
	    puts("1");
	    return ;
	}
	//
	while(a.size()){
	    auto t=a.front();a.pop();
	    for(int i=0;i<4;i++){
	        int x=t.x+dx[i];
	        int y=t.y+dy[i];
	        if(d1[x][y]!=inf||g[x][y]!='.')continue;
	        if(x&&y&&x<=n&&y<=m){
	            d1[x][y]=d1[t.x][t.y]+1;
	            a.push({x,y});
	        }
	    }
	}
	//
	while(b.size()){
	    auto t=b.front();b.pop();
	    for(int i=0;i<4;i++){
	        int x=t.x+dx[i];
	        int y=t.y+dy[i];
	        if(d2[x][y]!=inf||g[x][y]!='.'||d2[t.x][t.y]+1>=d1[x][y])continue;
	        if(x&&y&&x<=n&&y<=m){
	            d2[x][y]=d2[t.x][t.y]+1;
	            if(x==1||x==n||y==1||y==m){
	                cout<<d2[x][y]+1<<endl;
	                return ;
	            }
	            b.push({x,y});
	        }
	    }
	}
	puts("IMPOSSIBLE");
}
int main(){
    cin>>_;while(_--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

1076. 迷宫问题 - AcWing题库

题意

​ 在一个二维迷宫中，求从左上角到达右下角的最短路径，题目保证一定有解，需要输出最短路径（多个答案输出任意一组）。

题解

​ 这个就是一般的 $BFS$ 求最短路问题，但是要加上路径的存储。首先想到直接使用字符串去存储路径，然后很快啊、直接 $MLE$。只能换一种思路，可以记录当前点是从哪一点来的，但是要是还是从 $(0,0)$ 走的话就难以确定下一点的位置，于是可以反过来进行 $BFS$，这样在顺序输出的时候下一点就是唯一确定的了。

#include
#include
#include
using namespace std;
#define x first
#define y second
typedef pair<int,int>pii;
const int N=1010;
const int inf=0x3f3f3f3f;
pii dist[N][N];
int n,g[N][N];
bool st[N][N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void bfs(){
    queue<pii>q;
    q.push({n-1,n-1});
    st[n-1][n-1]=true;
    while(q.size()){
        auto t=q.front();q.pop();
        for(int i=0;i<4;i++){
            int x=t.x+dx[i];
            int y=t.y+dy[i];
            if(g[x][y]!=0||st[x][y])continue;
            if(x>=0&&y>=0&&x<n&&y<n){
                st[x][y]=true;
                dist[x][y]=t;
                q.push({x,y});
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    bfs();
    pii d={0,0};
    cout<<"0 0"<<endl;
    while(d.x!=n-1||d.y!=n-1){
        cout<<dist[d.x][d.y].x<<" "<<dist[d.x][d.y].y<<endl;
        int x=d.x,y=d.y;
        d.x=dist[x][y].x,d.y=dist[x][y].y;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

4225. 石油储备 - AcWing题库

题意

​ 给定一个 $n\times m$ 的二维矩阵，“@” 表示石油，“*” 是空地，若在一个石油的周围（八个方向）也存在石油，则这两块石油视为同一油田，求图中一共有多少块油田。

题解

​ 直接 $DFS$，判断周围还有没有石油。

#include
#include
using namespace std;
#define x first
#define y second
typedef pair<int,int>pii;
const int N=110;
int n,m;
char g[N][N];
int dx[]={1,1,0,-1,-1,0,1,-1};
int dy[]={1,0,1,-1,0,-1,-1,1};
void dfs(int x,int y){
    g[x][y]='*';
    for(int i=0;i<8;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx&&yy&&xx<=n&&yy<=m){
            if(g[xx][yy]=='@')dfs(xx,yy);
        }
    }
}
int main(){
    while(cin>>n>>m,n&&m){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>g[i][j];
        int ans=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(g[i][j]=='@'){
                    ans++;
                    dfs(i,j);
                }
            }
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

4226. 非常可乐 - AcWing题库

题意

​ 给定一罐容积为 $S$ 的可乐（满满一瓶），还有两颗容积为 $N$ 和 $M$ 的罐子，求最少多少的倒入倒出操作能将可乐分为两半。

题解

数学证明：

#include 
using namespace std;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int a,b,c;
    while(cin>>a>>b>>c&&(a&&b&&c)){
        a/=gcd(b,c);
        if(a&1)puts("NO");
        else cout<<a-1<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4227. 找路 - AcWing题库

题意

​ 给定一个 $n\times m$ 的矩阵，其中存在障碍、空地和餐馆，小 $Y$ 和小 $M$ 在矩阵的两个坐标上，求两人到同一个餐馆的最短距离和。

题解

​ 直接 $BFS$ 出两人到每一个餐馆的最小距离，再进行枚举。

#include
#include
#include
using namespace std;
#define x first
#define y second
typedef pair<int,int>pii;
const int N=210;
const int inf=0x3f3f3f3f;
int n,m,d1[N][N],d2[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
char g[N][N];
void bfs(int dist[N][N],int s0,int t0){
    queue<pii>q;
    q.push({s0,t0});
    dist[s0][t0]=0;
    while(q.size()){
        auto t=q.front();q.pop();
        for(int i=0;i<4;i++){
            int x=t.x+dx[i];
            int y=t.y+dy[i];
            if(x&&y&&x<=n&&y<=m&&g[x][y]!='#'&&dist[x][y]==-1){
                dist[x][y]=dist[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
}
int main(){
    while(cin>>n>>m){
        memset(d1, -1, sizeof d1);
        memset(d2, -1, sizeof d2);
        int xy,yy,xm,ym;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                cin>>g[i][j];
                if(g[i][j]=='Y')xy=i,yy=j;
                else if(g[i][j]=='M')xm=i,ym=j;
            }
        bfs(d1,xy,yy);
        bfs(d2,xm,ym);
        int res=inf;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]=='@'&&d1[i][j]>0&&d2[i][j]>0){
                    res=min(res,d1[i][j]+d2[i][j]);
                }
            }
        }
        cout<<11*res<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54