简单搜索

kuangbin专题一

简单搜索

棋盘问题
大致的解法就是，通过枚举每一行,之后选定列，选定之后再将该列标记，以免之后的行上面选到这一列

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 11;
char g[N][N];
int n,k;
int m;
int ans;
bool line[N];//存列也没有其他棋子
void dfs(int u)
{
    if( m == k)
    {
        ans++;
        return ;
    }
    if(u == n) return ;//防止越界
    
    for(int i=0;i<n;++i)//枚举
    {
        if(!line[i] && g[u][i] == '#')
        {
            line[i] = true;
            m++;
            dfs(u+1);
            m--;
            line[i] = false;
        }
    }
    dfs(u+1);//

}

int main()
{
   while(cin>>n>>k , n!=-1 && k != -1)
   {
        m = ans = 0;
        for(int i=0;i<n;++i)
            for(int j= 0;j<n;++j)
                cin>>g[i][j];
        dfs(0);//枚举行数
        cout<<ans<<endl;
   }
   return 0;
}

地牢大师
抛去三维不谈，这就是一道简单的板子题，可是这个是一道三维题，其中的坐标偏移量和平常所做的大不相同，所以得注意一下

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
struct map
{
   int l , r, c;   
};
map st,ed;
int l,c,r;
char g[N][N][N];
int dist[N][N][N];
int dx[] = {1,-1,0,0,0,0};
int dy[] = {0,0,1,-1,0,0};
int dz[] = {0,0,0,0,1,-1};

int bfs()
{
   queue<map> q;
   memset(dist ,-1,sizeof dist);
   q.push(st);
   dist[st.l][st.r][st.c] = 0;
   while(q.size())
   {
      auto t = q.front();
      q.pop();
      for(int i=0;i<6;++i)
      {
         int x = t.l+dx[i];
         int y = t.r+dy[i];
         int z = t.c+dz[i];
         if(x<0 || x>=l || y<0 || y>=r || z<0 || z>=c) continue;
         if(g[x][y][z] == '#') continue;
         if(dist[x][y][z] != -1) continue;
         dist[x][y][z] = dist[t.l][t.r][t.c] + 1;
         q.push({x,y,z});
         if(x == ed.l && y == ed.r && z == ed.c) return dist[x][y][z];
         
      }
   }
   return -1;
}

int main()
{
   while(scanf("%d%d%d",&l,&r,&c),l||r||c)
   {
      for(int i=0;i<l;++i)
         for(int j = 0;j<r;++j)
            {
                scanf("%s",g[i][j]);
                for(int k = 0;k<c;++k)
                {
                    char cc = g[i][j][k];
                    if(cc == 'S') st = {i,j,k};
                    else if(cc == 'E') ed = {i,j,k};
                }
            }
      int t = bfs();
      if(t == -1) puts("Trapped!");
      else printf("Escaped in %d minute(s).\n",t);
   }
   return 0;
}

抓住那头牛
农夫有三种移动方式，分别是x+1,x-1,x*2
求的是最短什么时候能抓住牛，dist[i]的含义就是从农夫的起点到i点所花费的最少时间，我们可以得出第一次走到这个点的时候就是从起点到这个点的最短时间。所以我们通过bfs进行搜索，搜索到了牛的点即停下来。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
int n,k;
int dist[N];
int bfs()
{
	queue<int> q;
	q.push(n);
	memset(dist,-1,sizeof dist);
	dist[n] = 0 ;
	while(!q.empty())
	{
		auto t = q.front();
		q.pop();
		if(t == k) return dist[k];
		if(t+1 < N && dist[t+1] == -1) dist[t+1] = dist[t] + 1,q.push(t+1);
		if(t+-1 >= 0 && dist[t-1] == -1) dist[t-1] = dist[t] + 1,q.push(t-1);
		if(t*2 < N && dist[t*2] == -1) dist[t*2] = dist[t] + 1,q.push(t*2);
	} 
	return -1;
}
int main()
{
	cin >> n >> k ;
	cout << bfs() << endl;
	return 0;
}

翻转
因为按下一个会影响他周围4个的值，所以我们先单独考虑。如果第一排的按下状态是固定的，我们就考虑第二排，因为我们最终是想要得到一个全0的状态，所以当第二排的某个位置对应的第一排有1的时候，我们必须按下第二排的那个位置，才能改变上一排那个位置的值。
所以我们可以通过枚举第一排的状态，剩下的排的状态都是固定的，都是根据它上一排的状态而定，我们只需要判断是不是全0就知道第一排的状态是否正确，这里我采用二进制枚举的方式进行枚举第一排。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 16;
int n,m;
int g[N][N];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int back[N][N];
int zero[N][N];
int ans[N][N];
int main()
{
    cin>>n>>m;


    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            cin>>g[i][j];
    memcpy(back,g,sizeof g);
    
    auto turn = [&](int x,int y){
        g[x][y] ^=1;
        for(int i=0;i<4;++i)
        {
            int tx = x+dx[i];
            int ty = y+dy[i];
            if(tx<0 || tx>n || ty<0 || ty>m) continue;
            g[tx][ty]^=1;
        }
    };
    bool find = false;
    for(int i=0;i<(1<<m);++i)
    {
        memcpy(g,back,sizeof back);
        memset(ans,0,sizeof ans);
        for(int j=0;j<m;++j)//
            if(i>>j &1) turn(0,j),ans[0][j] = 1;
        for(int j=0;j<n-1;++j)
            for(int k=0;k<m;++k)
                if(g[j][k])
                    turn(j+1,k),ans[j+1][k] = 1;
        bool flag_check = true;
        for(int k = 0;k<m;++k)
            if(g[n-1][k])
                flag_check = false;
        if(flag_check)
        {
            find = true;
            break;
        }
    }
    if(find)
    {
        for(int i=0;i<n;++i)
        {    
            for(int j=0;j<m;++j)
            {
                cout<<ans[i][j]<<' ';
            }
            cout<<endl;
        }   
    }
    else
    {
        puts("IMPOSSIBLE");
    }
   return 0;
}

找倍数
题意很简单，找到一个只由01构造的x的非零倍数,也就是说这个数字必须被x整除
我们直接从1开始拓展，只能拓展成两种状态,加1或者加0
因为数据太大，有$10^{100}$,根本存不下来，但是根据(a*b) % p = (a%p * b%p) % p，我们可以边计算边取模，并不会影响我们的答案。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int x;
typedef pair<string,int> PII;


string bfs(int x)
{
    queue<PII> q;
    q.push({"1",1});//从1开始拓展
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        if(!t.second) return t.first;
        q.push({t.first+"0" , (t.second * 10 ) % x});
        q.push({t.first+"1" , (t.second * 10 + 1 ) % x});
    }
    return "-1";
}

int main()
{
    while(cin>>x,x)
    {
        cout<<bfs(x)<<endl;
    }
   return 0;
}

质数路径
题意就是给我们一个数a，b让我们求多少步才能做到，并且要求每一步得到的数都是一个质数。
我们可以先把所有在数据范围内的质数筛出来，可以更方便的判断，之后就是bfs，状态就是10个数字和更换的位置，因为数据范围特殊，所以这个所谓的二重循环很小。注意细节上的判断即可,前导0等。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio                      \
	ios_base::sync_with_stdio(0); \
	cin.tie(0);                   \
	cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const int N = 1e5;
int primes[N], cnt;
bool st[N];
int d[4]={1,10,100,1000};
void get_primes(int n)
{
	for (int i = 2; i <= n; ++i)
	{
		if (!st[i])
			primes[cnt++] = i;
		for (int j = 0; primes[j] * i <= n; ++j)
		{
			st[primes[j] * i] = true;
			if (i % primes[j] == 0)
				break;
		}
	}
}
void fun()
{
	int a,b;
	cin >> a >> b;
	vector<int> dist(N,-1);
	dist[a] = 0;
	queue<int> q;
	q.push(a);
	while(q.size())
	{
		int t = q.front();
		q.pop();
		int t2 = t;
		if(t == b)
		{
			cout << dist[t] << nl;
			return ;
		}
		vector<int> bit;
		while(t2)//3才为最高位
		{
			bit.push_back(t2%10);
			t2/=10;
		}
		for(int i=0;i<=9;++i)
		{
			for(int j=0;j<4;++j)
			{
				auto &x = bit[j];//将要替换的数字
				if(x == i) continue;//数字相同
				if(i % 2 == 0 && j == 0) continue;//最低位是偶数，则跳过
				if(i == 0 && j == 3) continue;//不能有前导0
				int num = t - (x * d[j]) + (i * d[j]);//新的数
				if(num < 1000) continue;
				if(st[num]) continue;//不是素数
				if(dist[num] != -1) continue;//更新过了
				dist[num] = dist[t] + 1;
				q.push(num);
				
			}
		}
	}
}
int main()
{
	get_primes(N + 1);
	int t;
	cin >> t;
	while (t--)
		fun();
	return 0;
}

洗牌
就是对两个字符串的操作，问能不能变成指定状态，给了一个指定的状态转移，我们直接模拟实现这一步即可，就是很普通的搜索。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
int n;
string a, b, s;
string str_change(string a, string b)
{
    string tm;
    for (int i = 0; i < n; ++i)
    {
        tm += b[i];
        tm += a[i];
    }
    return tm;
}
inline int fun()
{
    cin >> n >> a >> b >> s;
    unordered_map<string, int> dist;
    string start = str_change(a, b);
    dist[start] = 1;
    queue<string> q;
    q.push(start);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        if(t == s)
            return dist[t]; 
        string new_str = str_change(t.substr(0,n),t.substr(n));
        if(dist.count(new_str)) continue;
        dist[new_str] = dist[t] + 1;
        q.push(new_str);
    }
    return -1;
}
int main()
{
    int t;
    cin >> t;
    for(int i=1;i<=t;++i)
    {
        cout << i << " ";
        cout << fun() << nl;
    }
    return 0;
}

罐子
两个罐子，一共有六种状态,状态存储，使用一个二维数组来存储，i是第一个罐子的状态，j是第二个。值得注意的是边界的判断很重要，不然可能不是最优解,导致心态炸裂。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
string choice[] = {"NULL", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
const int N = 110;
string s[N][N];
bool d[N][N];
string ans;
void bfs(int a, int b, int c)
{
    queue<PII> q;
    q.push({0, 0});
    d[0][0] = 1;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        auto &x = t.first;
        auto &y = t.second;
        if (x == c || y == c)
        {
            ans = s[x][y];
            break;
        }
        string &ns = s[x][y];
        // FILL和DROP
        if (!d[a][y])
            d[a][y] = 1, q.push({a, y}), s[a][y] = ns + '1';
        if (!d[x][b])
            d[x][b] = 1, q.push({x, b}), s[x][b] = ns + '2';
        if (!d[0][y])
            d[0][y] = 1, q.push({0, y}), s[0][y] = ns + '3';
        if (!d[x][0])
            d[x][0] = 1, q.push({x, 0}), s[x][0] = ns + '4';
        // POUR
        if (x > 0 && y < b)
        {
            int w = min(x, b - y);
            if (!d[x - w][y + w])
            {
                d[x - w][y + w] = 1;
                q.push({x - w, y + w});
                s[x - w][y + w] = ns + '5';
            }
        }
        if (x < a && y > 0)
        {
            int w = min(a - x, y);
            if (!d[x + w][y - w])
            {
                d[x + w][y - w] = 1;
                q.push({x + w, y - w});
                s[x + w][y - w] = ns + '6';
            }
        }
    }
    if (ans.size() == 0)
    {
        cout << "impossible" << nl;
    }
    else
    {
        cout << ans.size() << nl;
        for (int i = 0; i < ans.size(); ++i)
        {
            int x = ans[i] - '0';
            cout << choice[x] << nl;
        }
    }
}

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    bfs(a, b, c);
    return 0;
}

点火游戏
题意大概是，有草地和空地，让我们点燃一块或者两块草地，问最少需要多少时间可以让所有草地燃烧，空地不能被点燃。最优解肯定是能选两个就选两个，但是如果没办法就只能选0个或者不选（没有草地）。要小心一些特殊例子，不然很容易WA掉。还要注意草地循环的方式，得优化一半，不然会TLE。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;
typedef long long LL ;
typedef pair<int,int> PII;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const int N = 11;
int g[N][N];//1代表空地，0代表草地
int d[N][N];
int n,m,tot;//tot代表草地的数量
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
PII gress[N * N * 2];//草地的坐标
int ans;
int bfs(int a,int b)
{
    int tmp_ans = -2;
    int fire = 0;
    memset(d,-1,sizeof d);
    auto &u = gress[a];
    auto &v = gress[b];
    queue<PII> q;
    q.push(u);
    q.push(v);//防止重复
    if(u == v) q.pop();
    d[u.first][u.second] = 0;
    d[v.first][v.second] = 0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        fire ++ ;
        tmp_ans = max(tmp_ans,d[t.first][t.second]);
        for(int i=0;i<4;++i)
        {
            int x = dx[i] + t.first;
            int y = dy[i] + t.second;
            if(x < 0 || y < 0 || x>=n || y>=m) continue;//界限
            if(g[x][y]) continue;//空地
            if(d[x][y] != -1) continue;//有火

            d[x][y] = d[t.first][t.second] + 1;
            q.push({x,y});
        }
    }
    if(tot != fire) {return -1;}
    return tmp_ans;
}
void fun()
{
    ans = 0x3f3f3f3f;
    tot = 0;
    cin >> n >> m;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
        {
            char tmp;cin >> tmp;
            if(tmp == '#') g[i][j] = 0,gress[tot ++ ] = {i,j};
            else g[i][j] = 1;
        }
    for(int a=0;a<tot;++a)
        for(int b=a;b<tot;++b)
        {
            int sw = bfs(a,b);
            if(sw < 0) continue;
            ans = min(ans,sw);
        }
    if(ans == 0x3f3f3f3f) cout << "-1\n";
    else cout << ans << nl;
}
int main()
{
    _fio
    int t;cin >> t;for(int i=1;i<=t;++i){
        cout << "Case " << i << ": ";
        fun();
    }
    return 0;
}

起火迷宫
搜索两次,先预处理火到每个点的位置，之后搜索人能不能逃出去的路径，边界处理很重要，而且比较难调。wa过很多次。s

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL ;
typedef pair<int,int> PII;
const int N = 1010;
int g[N][N],d[N][N],f[N][N];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
int n,m;char c;

int main()
{
    _fio
    int T;cin >> T;
    while(T -- )
    {
        memset(g,0,sizeof g);
        memset(d,0,sizeof d);
        memset(f,0x3f,sizeof f);
        cin >> n >> m ;
        queue<PII> Q,F;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                if(cin >> c && c == '#') g[i][j] = 1;
                else if(c == 'J') Q.push({i,j}),d[i][j] = 1;
                else if(c == 'F') F.push({i,j}),f[i][j] = 1;
        while(F.size())
        {
            auto t = F.front();
            F.pop();
            for(int i=0;i<4;++i)
            {
                int a = dx[i] + t.first,b = dy[i] + t.second;
                if(g[a][b]) continue;
                if(f[a][b] == 0x3f3f3f3f)
                {
                    f[a][b] = f[t.first][t.second] + 1;
                    if(!(!a||!b||a == n+1 || b == m + 1)) F.push({a,b});
                }
            }
        }
        int ans = 1e9;
        while(Q.size())
        {
            auto t = Q.front();
            Q.pop();

            for(int i=0;i<4;++i)
            {
                int a = dx[i] + t.first,b = dy[i] + t.second;
                if(g[a][b] || d[t.first][t.second] + 1 >= f[a][b]) continue;
                if(d[a][b] == 0)
                {
                    d[a][b] = d[t.first][t.second] + 1;
                    if(!(!a||!b||a == n+1 || b == m + 1)) Q.push({a,b});
                    else if(d[a][b] < f[a][b]) ans = min(ans,d[a][b]);
                }
            }
        }
        if(ans == 1e9) cout << "IMPOSSIBLE\n";
        else cout << ans - 1 << endl;
    }
    return 0;
}

迷宫问题
本题就是考察一个记录迷宫路径问题，可以经常回顾。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int g[N][N];
queue<PII> q;
PII pre[N][N];
void bfs(int sx,int sy)
{
	q.push({sx,sy});
	memset(pre, -1 , sizeof pre);
	pre[sx][sy] = {0,0};
	while(!q.empty())
	{
		auto t = q.front();
		q.pop();
		for(int i=0;i<4;++i)
		{
			int a = t.x + dx[i];
			int b = t.y + dy[i];
			if(a < 0 || a>=n || b<0 || b>=n) continue;
			if(g[a][b]) continue;
			if(pre[a][b].x != -1) continue;
			q.push({a,b});
			pre[a][b] = t;
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			scanf("%d",&g[i][j]);
	bfs(n-1,n-1);
	PII end(0,0);
	while(true)
	{
		printf("%d %d\n",end.x,end.y);
		if(end.x == n-1 && end.y == n-1) break;
		end = pre[end.x][end.y];
	}
	return 0;
}

石油储备
经典Flood Fill问题,大致思路就是选一个点，遍历完周围所有点，结束时去下一个位置，一直检索，数出来连通块的个数。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const char nl = '\n';
const int INF = 0x3f3f3f3f;

const int N = 110;
int n, m, cnt;
char g[N][N];
bool st[N][N];
int dx[] = {-1,0,1,0,-1,1,-1,1};
int dy[] = {0,1,0,-1,-1,1,1,-1};
void bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    while (q.size())
    {
        auto t = q.front(); q.pop();
        for (int i = 0; i < 8; i++)
        {
            int a = dx[i] + t.first;
            int b = dy[i] + t.second;
            if(a < 0 || b < 0 || a>=n || b>=m) continue;
            if(g[a][b] == '*') continue;
            if(st[a][b]) continue;

            q.push({a,b});
            st[a][b] = 1; 
        }
        
    }
    
}
int main()
{
    while (cin >> n >> m, n,m)
    {
        cnt = 0;
        memset(st,0,sizeof st);
        for (int i = 0; i < n; ++i)
            cin >> g[i];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                if (!st[i][j] && g[i][j] == '@')
                {
                    st[i][j] = 1;
                    bfs(i, j);
                    cnt ++ ;
                }
            }
        cout << cnt << nl;
    }

    return 0;
}

非常可乐
类似于罐子那道题，条件比较难想

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;
typedef long long LL ;
typedef pair<int,int> PII;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const int N = 110;
bool st[N][N][N];
int v[3];
struct Node
{
    int a,b,c,w;
};
int bfs()
{
    queue<Node> q;
    memset(st,0,sizeof st);
    q.push({v[0],0,0,0});
    st[v[0]][0][0] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int u[3] = {t.a,t.b,t.c};
        if((u[0] == u[1] && !u[2]) ||
            (u[1] == u[2] && !u[0]) ||
            (u[2] == u[0] && !u[1]))
            {
                return t.w;
            }
        for(int i=0;i<3;++i)
            for(int j=0;j<3;++j)
                if(i!=j && u[i] && u[j] != v[j])//pour each other
                {
                    //backup
                    int ui = u[i];
                    int uj = u[j];
                    //i -> j
                    if(v[j]-u[j]<=u[i])
                    {
                        //no pour all
                        u[i] -= v[j] - u[j];
                        u[j] = v[j];
                    }
                    else
                    {
                        //pour all
                        u[j] += u[i];
                        u[i] = 0;
                    }
                    if(!st[u[0]][u[1]][u[2]])
                    {
                        st[u[0]][u[1]][u[2]] = true;
                        q.push(Node{u[0],u[1],u[2],t.w + 1});
                    } 
                    u[i] = ui;
                    u[j] = uj;  
                }
    }
    return -1;

}
int main()
{
    while(cin >> v[0] >> v[1] >> v[2],v[0],v[1],v[2])
    {
        int ans = bfs();
        if(ans == -1) cout << "NO" << nl;
        else cout << ans << nl;
    }
    return 0;
}

找路
分别按照两个点进行bfs即可,最终的答案就是两个人都可以到的餐厅的到达之间之和。

▶

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#define _fio                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const char nl = '\n';
const int INF = 0x3f3f3f3f;

const int N = 222;
int d1[N][N],d2[N][N];
char g[N][N];
/*
    Y : 小Y位置
    M : 小M位置
    # : 障碍
    . : 空地
    @ ：餐厅
*/
int n, m;
PII a, b;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void bfs1()
{
    queue<PII> q;
    q.push(a);
    d1[a.first][a.second] = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int tx = dx[i] + t.first;
            int ty = dy[i] + t.second;
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if(g[tx][ty] == '#') continue;
            if(d1[tx][ty] != -1) continue;
            d1[tx][ty] = d1[t.first][t.second] + 1;
            q.push({tx,ty});
        }
    }
}
void bfs2()
{
    queue<PII> q;
    q.push(b);
    d2[b.first][b.second] = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int tx = dx[i] + t.first;
            int ty = dy[i] + t.second;
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if(g[tx][ty] == '#') continue;
            if(d2[tx][ty] != -1) continue;
            d2[tx][ty] = d2[t.first][t.second] + 1;
            q.push({tx,ty});
        }
    }
}
int main()
{
    while (~scanf("%d %d",&n,&m))
    {
        vector<PII> v;
        memset(d1, -1, sizeof d1);
        memset(d2, -1, sizeof d2);
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin >> g[i][j];
                if (g[i][j] == 'Y')
                    a = {i, j};
                if (g[i][j] == 'M')
                    b = {i, j};
                if (g[i][j] == '@')
                    v.push_back({i, j});
            }
        }
        bfs1();
        bfs2();
        int ans = INF;
        for (auto el : v)
        {
            int x1 = d1[el.first][el.second];
            int x2 = d2[el.first][el.second];
            if(x1 != -1 && x2 != -1)
            ans = min(ans, x1 + x2);
        }
        cout << ans * 11 << nl;
    }
    return 0;
}

算法

#algorithm #kuangbin

简单搜索

http://pikachuxpf.github.io/posts/38402/

作者

Pikachu_fpx

发布于

2023年8月27日

许可协议

求逆序对的数量上一篇

时间复杂度下一篇