一本通刷题(One book brush questions)

一本通
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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


————————

All in one book
BFS part
one
http://ybt.ssoier.cn:8088/problem_show.php?pid=1329
A basic problem of finding connected blocks

#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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


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;
}


http://ybt.ssoier.cn:8088/problem_show.php?pid=1257
BFS find the shortest path, Japanese word path,

#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

Find the shortest path by 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;
}


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

For the selection problem, a trick is twice & lt= When K + 2 is selected, you can choose to multiply by two, which is better. Otherwise, subtract first and then 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;
}


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

It is also the shortest path problem of BFS. It only needs to print the path. The print path records the precursor, either while or back to write. It is very convenient

#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;
}