一本通刷题

一本通
BFS part
1
http://ybt.ssoier.cn:8088/problem_show.php?pid=1329
一道基础的求连通块的题目

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=1e3+52;
int n,m,ans;
bool st[N][N];
int d[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
char g[N][N];
PII point[N*N];
void bfs(int sx,int sy)
{
	int hh=0,tt=0;
	point[0]={sx,sy};
	st[sx][sy]=1;
	while(hh<=tt)
	{
		PII t=point[hh++];
		rep(i,0,4)
			rep(j,0,2)
			{
				int x1=t.x+d[i][0],y1=t.y+d[i][1];
				if(x1==t.x&&y1==t.y) continue;
				if(x1<0||x1>=n||y1<0||y1>=m) continue;
				if(g[x1][y1]=='0'||st[x1][y1]) continue;
				point[++tt]={x1,y1};
				st[x1][y1]=1; 
			}
	}
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{ 
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),m=read();
	rep(i,0,n) scanf("%s",g[i]);
	rep(i,0,n)
	{
		rep(j,0,m) 
			if(g[i][j]!='0'&&!st[i][j])
			 {
			 	bfs(i,j);
			 	ans++;
			 }	
	} 
	printf("%d\n",ans);  
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


2
http://ybt.ssoier.cn:8088/problem_show.php?pid=1249

floodfill计算连通块模型
点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
int n,m,ans;
char g[N][N];
int q[N];
bool st[N][N];
PII point[N*N];
void  bfs(int sx,int sy)
{
	int hh=0,tt=0;
	point[0]={sx,sy};
	st[sx][sy] =1;
	while(hh<=tt)
	{
		PII t=point[hh++];
		rep(i,t.x-1,t.x+2)
			rep(j,t.y-1,t.y+2)
			{
				if(i==t.x&&j==t.y) continue;
				if(i<0||i>=n||j<0||j>=m) continue;
				if(g[i][j]=='.'||st[i][j]) continue;
				point[++tt]={i,j};
				st[i][j]=1;
			 } 
	}
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),m=read();
	rep(i,0,n) scanf("%s",g[i]);
	rep(i,0,n)
		rep(j,0,m)
			if(!st[i][j]&&g[i][j]=='W')bfs(i,j),ans++;
    printf("%d\n",ans);
	end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


3
http://ybt.ssoier.cn:8088/problem_show.php?pid=1250

floodfill
点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=52;
int n,m;
int g[N][N];
bool st[N][N];
PII q[N*N];
int bfs(int sx,int sy)
{
	int d[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
	int hh=0,tt=0;q[0]={sx,sy};
	st[sx][sy]=1;
	int area=0;
	while(hh<=tt)
	{
		PII t=q[hh++];
		area++;
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=n||b<0||b>=m) continue;
			if(st[a][b]) continue;
			if(g[t.x][t.y]>>i&1) continue;
			q[++tt]={a,b};
			st[a][b]=1;
		}
	}
	return area;
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),m=read();
	rep(i,0,n) rep(j,0,m) g[i][j]=read();
	int cnt=0,area=0;
	rep(i,0,n) rep(j,0,m) if(!st[i][j]) area=max(area,bfs(i,j)),cnt++;
	printf("%d\n%d\n",cnt,area);
	end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


4
http://ybt.ssoier.cn:8088/problem_show.php?pid=1251
bfs求最短路
点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=52;
int n,m,cnt;
int sx,sy;
PII q[N*N];
char g[N][N];
int dis[N][N];//不需要d因为走过就有了距离 
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int bfs(int sx,int sy)
{
	q[0]={sx,sy};
	memset(dis,-1,sizeof(dis)); 
	dis[sx][sy]=0;
	int hh=0,tt=0;
	while(hh<=tt)
	{
		PII t=q[hh++];
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||b<0||a>=n||b>=m) continue;
			if(dis[a][b]!=-1||g[a][b]=='#') continue;
			dis[a][b]=dis[t.x][t.y]+1;	
			if(g[a][b]=='*') return dis[a][b]; 
			q[++tt]={a,b};
		 } 
	 } 
	 return -1;
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	while(cin >> n >> m, n || m)
    {
        for(int i = 0; i < n; i ++) cin >> g[i];

        for(int i = 0; i < n; i ++)
            // for(int j = 0; j < n; j ++)  // **3
            for(int j = 0; j < m; j ++)
                if(g[i][j] == '@')
                    sx=i,sy=j;
        cout << bfs(sx,sy) << endl;
    }

    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


5
http://ybt.ssoier.cn:8088/problem_show.php?pid=1252

bfs求最短路
点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=52;
int n,m;
char g[N][N];
PII q[N*N];
int dist[N][N];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int bfs(int sx,int sy)
{
	memset(dist,-1,sizeof(dist));
	int hh=0,tt=0;
	q[0]={sx,sy};
	dist[sx][sy]=1;
	while(hh<=tt)
	{
		PII t=q[hh++];
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=n||b<0||b>=m) continue;
			if(dist[a][b]!=-1||g[a][b]=='#') continue;
			dist[a][b]=dist[t.x][t.y]+1;q[++tt]={a,b};
		}
	}
	return dist[n-1][m-1];
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),m=read();
	rep(i,0,n) scanf("%s",g[i]);
	printf("%d\n",bfs(0,0));
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


6
http://ybt.ssoier.cn:8088/problem_show.php?pid=1254

bfs最短路
点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
int n,m;
char g[N][N];
int dist[N][N];
PII q[N*N];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int sx,sy;
int bfs(int sx,int sy){
	memset(dist,-1,sizeof(dist));
	int hh=0,tt=0;
	dist[sx][sy]=0;
	q[0]={sx,sy};
	while(hh<=tt)
	{
		PII t=q[hh++];
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=n||b<0||b>=m) continue;
			if(g[a][b]=='#'||dist[a][b]!=-1) continue;
			dist[a][b]=dist[t.x][t.y]+1;q[++tt]={a,b};
			if(g[a][b]=='T') return dist[a][b];
		}
	}
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	n=read(),m=read();
	rep(i,0,n) scanf("%s",g[i]);
	rep(i,0,n)
		rep(j,0,m)
			if(g[i][j]=='S') sx=i,sy=j;
    printf("%d\n",bfs(sx,sy));
	end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


7

http://ybt.ssoier.cn:8088/problem_show.php?pid=1256
bfs求最短路

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
int n,m,t;
char g[N][N];
PII q[N*N];
int dist[N][N];
int sx,sy;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int bfs(int sx,int sy)
{
	memset(dist,-1,sizeof(dist));
	int hh=0,tt=0;
	q[0]={sx,sy};
	dist[sx][sy]=0;
	while(hh<=tt)
	{
		PII t=q[hh++];
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=n||b<0||b>=m) continue;
			if(g[a][b]=='#'||dist[a][b]!=-1) continue;
			dist[a][b]=dist[t.x][t.y]+1,q[++tt]={a,b};
			if(g[a][b]=='E') return dist[a][b];
		}
	}	
	return -1;
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	t=read();
	while(t--)
	{
		n=read(),m=read();
		rep(i,0,n) scanf("%s",g[i]);
		rep(i,0,n) rep(j,0,m) if(g[i][j]=='S') sx=i,sy=j;
		int ans=bfs(sx,sy);
		if(ans==-1) puts("oop!");
		else printf("%d\n",ans);
	}
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


8

http://ybt.ssoier.cn:8088/problem_show.php?pid=1257
bfs求最短路,日字路径,

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
int t,n;
PII st,ed;
PII q[N*N];
int dist[N][N];
int d[8][2]={{-2,1},{-1,2},{-2,-1},{-1,-2},{1,2},{2,1},{1,-2},{2,-1}};
int bfs(int sx,int sy)
{
	memset(dist,-1,sizeof(dist));
	int hh=0,tt=0;
	q[0]={sx,sy};
	dist[sx][sy]=0;
	while(hh<=tt)
	{
		PII t=q[hh++];	
		rep(i,0,8)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=n||b<0||b>=n) continue;
			if(dist[a][b]!=-1) continue;
			dist[a][b]=dist[t.x][t.y]+1,q[++tt]={a,b};
			if(a==ed.x&&b==ed.y) return dist[a][b];
		}
	}	
}

int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	t=read();
	while(t--)
	{
		n=read();st.x=read(),st.y=read(),ed.x=read(),ed.y=read();
		if(st.x==ed.x&&st.y==ed.y) puts("0");
		else printf("%d\n",bfs(st.x,st.y));
	 } 
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


9
http://ybt.ssoier.cn:8088/problem_show.php?pid=1330

bfs求最短路

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=520;
int t,n;
PII st,ed;
PII q[N*N];
int dist[N][N];
int d[12][2]={{-2,1},{-1,2},{-2,-1},{-1,-2},{1,2},{2,1},{1,-2},{2,-1},{2,2},{-2,-2},{2,-2},{-2,2}};
int bfs(int sx,int sy)
{
	memset(dist,-1,sizeof(dist));
	int hh=0,tt=0;
	q[0]={sx,sy};
	dist[sx][sy]=0;
	while(hh<=tt)
	{
		PII t=q[hh++];	
		rep(i,0,12)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=100||b<0||b>=100) continue;
			if(dist[a][b]!=-1) continue;
			dist[a][b]=dist[t.x][t.y]+1,q[++tt]={a,b};
			if(a==0&&b==0) return dist[a][b];
		}
	}	
}

int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	t=1;
	while(t--)
	{
		st.x=read(),st.y=read(),ed.x=read(),ed.y=read();
		printf("%d\n",bfs(st.x-1,st.y-1));
		printf("%d\n",bfs(ed.x-1,ed.y-1)); 
	 } 
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


10

http://ybt.ssoier.cn:8088/problem_show.php?pid=1253

选择问题,有一个trick就是在两倍<=k+2的时候选择可以选择乘二,这样是更优的,否则先减再2

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=2e5+52;
int n,k;
int q[N];
int dist[N];
int bfs()
{
	memset(dist,-1,sizeof(dist));
	dist[n]=0;q[0]=n;
	int hh=0,tt=0;
	while(hh<=tt)
	{
		int t=q[hh++];
		if(t==k) return dist[k];
		if(t+1<=k&&dist[t+1]==-1) dist[t+1]=dist[t]+1,q[++tt]=t+1;
		if(t-1>=0&&dist[t-1]==-1) dist[t-1]=dist[t]+1,q[++tt]=t-1;
		if(t*2<=(k+3)&&dist[t*2]==-1) dist[t*2]=dist[t]+1,q[++tt]=t*2; 
	}
	return -1;
}

int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();	
    n=read(),k=read();
    printf("%d\n",bfs());
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


11

http://ybt.ssoier.cn:8088/problem_show.php?pid=1255

还是bfs最短路问题,只不过需要打印路径,打印路径记录前驱,要么while,要么递归来写,很方便

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=52;
PII q[N*N],pre[N][N];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; 
int dist[N][N];
int  g[N][N];
void print(int sx,int sy)
{
	if(sx==-1&&sy==-1) return; 
	print(pre[sx][sy].x,pre[sx][sy].y);
	printf("(%d, %d)\n",sx,sy);
}
void bfs(int sx,int sy)
{
	memset(dist,-1,sizeof(dist));
	int hh=0,tt=0;
	q[0]={sx,sy};
	pre[sx][sy]={-1,-1};
	dist[sx][sy]=0;
	while(hh<=tt)
	{
		PII t=q[hh++];
		rep(i,0,4)
		{
			int a=t.x+d[i][0],b=t.y+d[i][1];
			if(a<0||a>=5||b<0||b>=5) continue;
			if(dist[a][b]!=-1||g[a][b]==1) continue;
			dist[a][b]=dist[t.x][t.y]+1,q[++tt]={a,b},pre[a][b]={t.x,t.y}; 
		}
	}
	print(4,4);
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	rep(i,0,5) rep(j,0,5) g[i][j]=read();
	bfs(0,0); 
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


12
水水的三维bfs
http://ybt.ssoier.cn:8088/problem_show.php?pid=1248

点击查看代码
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=int(l);i<int(r);i++)
#define per(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define repg(i,l,r) for(i=int(l);i<int(r);i++)
#define perg(i,r,l) for(int i=int(r-1);i>=int(l);i--)
#define rept(i,t) for(int i=int(h[t]);~i;i=ne[i])
#define reph(i,t,h) for(int i=int(h[t]);~i;i=ne[i])
#define x first
#define y second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long lll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF=0x3f3f3f3f,mod=1e9+7;
const ll INFF=1e18;
const double eps=1e-9;
mt19937 mrand(random_device{}());
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    rep(i, 0, sz(v)) {
        if(i) out << " ";
        out << v[i];
    }
    return out;
}
int rnd(int x){return mrand()%x;}
ll qmi(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll qmul(ll a,ll b){ll res=0;a%=mod;while(b){if(b&1) res=(res+a)%mod;a=(a+a)%mod;b>>=1;} return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}*/
//#include <iostream>
//#include <cstdio>
//#include <windows.h>
//#include <cstdlib>
//#include <ctime>
//using namespace std;
//int main()
//{
//    int ok = 0;
//    int n = 50;
//    for (int i = 1; i <= n; ++i)
//    {
//        system("make.exe > make.txt");
//        system("std.exe < make.txt > std.txt");
//        double begin = clock();
//        system("baoli.exe < make.txt > baoli.txt");
//        double end = clock();
//
//        double t = (end - begin);
//        if (system("fc std.txt baoli.txt"))
//        {
//            printf("测试点#%d Wrong Answer\n", i);
//        }
//        else if (t > 1000) //1秒
//        {
//            printf("测试点#%d Time Limited Exceeded 用时 %.0lfms\n", i, t);
//        }
//        else
//        {
//            printf("测试点#%d Accepted 用时%.0lfms\n", i, t);
//            ok++; //AC数量+1
//        }
//    }
//    printf("\n");
//    double res = 100.0 * ok / n;
//    printf("共 %d 组测试数据,AC数据 %d 组。 得分%.1lf。", n, ok, res);
//
//    Sleep(1000); //休眠1秒,为了节约对拍次数。
//}
inline int read()
{
    int x=0;
    char ch;
    bool fx=false;
    do ch=getchar();while(~ch&&ch!='-'&&(ch<48||ch>57));
    if(ch=='-')fx=true,ch=getchar();
    for(;ch>47&&ch<58;ch=getchar())
        x=(x<<1)+(x<<3)+(ch^48);
    return fx?-x:x;
}
const int N=52;
char g[N][N][N];
int d[6][3]={{1,0,0},{0,1,0},{-1,0,0},{0,-1,0},{0,0,1},{0,0,-1}};
int dist[N][N][N];
int h,n,m;
int sz,sx,sy;
struct point
{
	int z,x,y;
}q[N*N*N];
int bfs(int sz,int sx,int sy)
{
	memset(dist,-1,sizeof(dist));
	int hh=0,tt=0;
	q[0]={sz,sx,sy};
	dist[sz][sx][sy]=0;
	while(hh<=tt)
	{
		point t=q[hh++];
		rep(i,0,6)
		{
			int c=t.z+d[i][0],a=t.x+d[i][1],b=t.y+d[i][2];
			if(c<0||c>=h||a<0||a>=n||b<0||b>=m) continue;
			if(g[c][a][b]=='#'||dist[c][a][b]!=-1) continue;
			dist[c][a][b]=dist[t.z][t.x][t.y]+1;q[++tt]={c,a,b}; 
			if(g[c][a][b]=='E') return dist[c][a][b];
 		} 
	}
	return -1;
}
int main()
{
#ifdef my_test
 	freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef my_dp
	while(1)
	{
		system("data.exe > in.txt");
		system("brute.exe < in.txt > brute.txt");
		system("std.exe < in.txt > std.txt");
		if(system("fc std.txt brute.txt"))
			break;
	}
#endif
#ifdef my_dp2
    while (1) //一直循环,直到找到不一样的数据
    {
        system("data.exe");
        system("baoli.exe");
        system("std.exe");
        if (system("fc std.txt baoli.txt")) //当 fc 返回1时,说明这时数据不一样
            break;                          //不一样就跳出循环
    }
#endif
	clock_t start,end;
    start=clock();
	while(h=read(),n=read(),m=read(),h,n,m)
	{
		rep(i,0,h) rep(j,0,n) scanf("%s",g[i][j]);
		rep(i,0,h) rep(j,0,n) rep(k,0,m) if(g[i][j][k]=='S')  sz=i,sx=j,sy=k;
		int ans=bfs(sz,sx,sy);
		if(ans==-1)puts("Trapped!");
		else printf("Escaped in %d minute(s).\n",ans);
	} 
    end=clock();
//    printf("%lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
    return 0;
}


上一篇:Windows Server 2022 英文版、简体中文版下载 (updated Dec 2021)(2022 年 1 月发布)


下一篇:C++多线程学习笔记06(单例设计模式)