深基刷题记录（3）

深碍√TFBOYSˉ_ 2023-02-14 02:48 26阅读 0赞

# P1219 \[USACO1.5\]八皇后 Checker Challenge #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]

#include<bits/stdc++.h>
    using namespace std;
    int a[100],b[100],c[100],d[100];
    //a数组表示的是行；
    //b数组表示的是列；
    //c表示的是左下到右上的对角线；
    //d表示的是左上到右下的对角线；
    int total;//总数:记录解的总数
    int n;//输入的数，即N*N的格子，全局变量，搜索中要用
    int print()
    { 
        if(total<=2)//保证只输出前三个解，如果解超出三个就不再输出，但后面的total还需要继续叠加
        { 
            for(int k=1;k<=n;k++)
            cout<<a[k]<<" ";//for语句输出
            cout<<endl;
        }
        total++;//total既是总数，也是前三个排列的判断
    }
    void queen(int i)//搜索与回溯主体
    { 
        if(i>n)
        { 
            print();//输出函数，自己写的
            return;
        }
        else
        { 
            for(int j=1;j<=n;j++)//尝试可能的位置
            { 
                if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果没有皇后占领，执行以下程序
                { 
                    a[i]=j;//标记i排是第j个
                    b[j]=1;//宣布占领纵列
                    c[i+j]=1;
                    d[i-j+n]=1;
                    //宣布占领两条对角线
                    queen(i+1);//进一步搜索，下一个皇后
                    b[j]=0;
                    c[i+j]=0;
                    d[i-j+n]=0;
                    //（回到上一步）清除标记
                }
            }
        }
    }
    int main()
    {     
        cin>>n;//输入N*N网格，n已在全局中定义
        queen(1);//第一个皇后
        cout<<total;//输出可能的总数
        return 0;
    }

# P1605 迷宫 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 2]

#include<bits/stdc++.h>
    using namespace std;
    int n,m,k,x,y,a,b,ans;
    int dx[4] = { 0,0,1,-1},dy[4] = { 1,-1,0,0};
    bool vis[6][6];
    struct Node{ 
        int x,y,used[6][6];
    }sa;
    int main()
    { 
        scanf("%d%d%d",&n,&m,&k);
        scanf("%d%d%d%d",&x,&y,&a,&b);         //虽然这里可以合并成一个句子，但是由于我是从python转过来的，建议大家以后写代码都设置一个界限，代码不宜太长
        for(int i = 1,aa,bb;i <= k; i++)     //大家注意一下，我现在是直接把变量定义在循环里面。
        { 
            scanf("%d%d",&aa,&bb);           //现在我们不能走障碍了。
            vis[aa][bb] = 1;
        }
        queue<Node> q;      //定义结构体后，可以直接使用结构体名定义变量或者队列。
        sa.x = x;
        sa.y = y;         //横纵坐标替换，这样写起来方便。
        sa.used[x][y] = 1;//标记走过的路径
        q.push(sa);
        while(!q.empty())
        { 
            Node now = q.front();     //一起拿出来
            q.pop();
            for(int i = 0;i < 4; i++)
            { 
                int sx = now.x + dx[i];
                int sy = now.y + dy[i];
                if( now.used[sx][sy] 
                    || vis[sx][sy] 
                    || sx == 0 || sy == 0 
                    || sx > n || sy > m)
                    continue;    //如果这里走过，或者这里是障碍，或者这里是墙壁，那么这里就不能走。
                if(sx == a && sy == b)
                { 
                    ans++;           //如果这里是终点，那么结果数量加一
                    continue;
                }
                sa.x = sx;
                sa.y = sy;
                memcpy(sa.used,now.used,sizeof(now.used));
                sa.used[sx][sy] = 1;     //这里的操作都是为了标记路径
                q.push(sa);
            }
        }
        printf("%d",ans);
        return 0;
    }

**bfs 正确代码的习惯：**  
1、bfs 不写 check  
2、写两个 if，第一个相当于 check，后面跟 continue  
3、很少写 `q.push((node){a,b})` ，这样的省略写法  
4、用 dx 和 dy 两个数组表示上下左右  
**关于此题：**  
在结构体中用了记录路径的数组防止 TLE

# P1019 单词接龙 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 3]

#include<bits/stdc++.h>
    using namespace std;
    const int N=30;
    int chu[N];
    string t[N],str;
    int n,maxx;
    int gao(string x,string q)//找是否可以相连 
    { 
    	for(int i=x.size()-1;i>=0;i--)//倒的找找到一个就退出这样肯定是最优的 
    	{ 
    		if(x[i]==q[0])//如果和匹配开头一样就开始找是否合法 
    		{ 
    			int l=i;//当前开始的位置 
    			for(int j=0;j<q.size();j++){ if(x[l]==q[j])l++;else break;}//如果一样的话就一直找否则就退出来，必须退！ 
    			if(l==x.size())return l-i;//如果找完了就算出有多少个是匹配的这个就是重复的值 
    		}
    	}
    	return 0;//没有就返回0回去；
    }
    void dfs(int fu,string x)
    { 
    	maxx=max(maxx,(int)x.size()-fu);//用字符的长度减去重复的长度 
    	for(int i=1;i<=n;i++)//找接在后面的单词 
    	{ 
    		int duan=0;
    		if(chu[i]==2)continue;//一个单词可以用两次，如果用过两次就直接跳
    		duan=gao(x,t[i]);//duan为他们重叠的长度 
    		if(!duan)continue;//如果为0没重叠就直接跳过(很重要！) 
    		chu[i]++;//这个位置标记一下表示用过 
    		dfs(fu+duan,x+t[i]);//重叠的部分相加字符串更新 
    		chu[i]--;//回溯 
    	}
    	return ;//没找有一个匹配就返回 
    }
    int main()
    { 
    	cin>>n;
    	for(int i=1;i<=n;i++)cin>>t[i];//把每个都存起来 
    	cin>>str;
    	dfs(0,str);
    	cout<<maxx;//最大长度 
    	return 0;
    }

注意感叹号部分，那些部分是必须加的（而不是为了省时间）

# P1101 单词方阵 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 5]

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxn=100+10;
    struct node
    { 
        int x,y;
    }c[maxn];//记录路径
    char fz[maxn][maxn],stand[]="yizhong";//fz保存单词矩阵，stand保存保准的“yizhong”便于匹配
    int vis[maxn][maxn];//保存路径，是否该点为答案
    int dir[][2]={ { -1,-1},{ -1,0},{ -1,1},{ 0,-1},{ 0,1},{ 1,-1},{ 1,0},{ 1,1}};//八向的常量数组
    void dfs(int x,int y,node c[],int k,int cur)
    { 
        if(cur==7){ 
            for(int i=0;i<7;i++)
                vis[c[i].x][c[i].y]=1;
        }
        else{ 
            int dx=x+dir[k][0];//沿着正确的k方向搜索
            int dy=y+dir[k][1];
            if(cur==6||fz[dx][dy]==stand[cur+1]){ //当cur是6的时候就已经完成了(因为单词是7个字母) 
                c[cur].x=x;c[cur].y=y;
                dfs(dx,dy,c,k,cur+1);
            }
        }
    }
    int main()
    { 
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%s",fz[i]); //一次存储一行 
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)//搜索y，i相连的可能的方向k，以k为方向进行DFS
            for(int j=0;j<n;j++)
                if(fz[i][j]=='y')
    				for(int k=0;k<8;k++)
    				{ 
                        int x=i+dir[k][0];
                        int y=j+dir[k][1];
                        if(fz[x][y]=='i')
                            dfs(i,j,c,k,0);//注意是从 i j 开始 
                    }
        for(int i=0;i<n;i++){ //输出结果
            for(int j=0;j<n;j++)
                if(vis[i][j]) printf("%c",fz[i][j]);
                else printf("*");
            printf("\n");
        }
        return 0;
    }

**dfs 正确代码的习惯：**  
1、写 dir 二维数组表示方向  
**关于此题：**  
1、此代码定义了结构体数组，用于记录路径  
2、之所以先找 y 和 i 是因为要用 k 确定方向（也可以不用先找 y 和 i ）  
3、字符串一次存一行

# P1443 马的遍历 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 6]

#include<bits/stdc++.h> 
    using namespace std;
    struct xy{ 
        int x,y;
    }node,Top;
    const int dx[4]={ 1,-1,2,-2};
    const int dy[4]={ 1,-1,2,-2};//虽说一共16个方向 但是在程序中有具体判断
    int a[401][401];
    bool b[401][401]; 
    int n,m;
    int main(){ 
        memset(b,true,sizeof(b));
        memset(a,-1,sizeof(a));
        int x,y;
        scanf("%d%d%d%d" ,&n ,&m ,&x ,&y );
        a[x][y] = 0;
        b[x][y] = false;
        queue<xy> Q;//构建队列
        node.x = x;
        node.y = y;
        Q.push(node);//起始点入队
        while (!Q.empty()){ 
            Top=Q.front();//取出队首点
            Q.pop();//队首点出队
                for (int i=0;i<4;i++)
                    for (int j=0;j<4;j++)
                        if (abs(dx[i])!=abs(dy[j])){ //判断方向
                            int NewX=Top.x+dx[i];
                            int NewY=Top.y+dy[j];
                            if (NewX<1||NewX>n||NewY<1||NewY>m) continue;//判断越界
                            if (b[NewX][NewY]){ //使用布尔数组保证每个点只入队一次 时间复杂度明显低于DFS
                                node.x=NewX;
                                node.y=NewY;
                                Q.push(node);
                                b[NewX][NewY] = false;//标记已入队
                                a[NewX][NewY] = a[Top.x][Top.y]+1;//路径+1
                            }
                        }
        }
        for (int i=1;i<=n;i++){ 
            for (int j=1;j<=m;j++)
                printf("%-5d", a[i][j]);//-5d是向左对其，并有 5格 
            printf("\n");
        }
        return 0;
    }

**重点提醒：**  
不能这样写：`bool b[405][405]={true};`  
要这样写：`fill(b[0],b[0]+401*401,true);`  
因为二维数组是不能直接用 **true** 的

# P2895 \[USACO08FEB\]Meteor Shower S #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 8]

#include<bits/stdc++.h>
    using namespace std;
    struct node
    { 
    	int x,y,time;
    } p; //x,y存坐标，time存当前的时间 
    int m,x,y,t,nx,ny,time1[305][305],c[305][305]; //time1数组存这个格子流星最早到达的时间，c存是否到过这个格子，数组开大点！！！！ 
    int b1[4]= { 0,0,1,-1},b2[4]= { 1,-1,0,0};
    queue<node>q;
    int main()
    { 
    	cin>>m;
    	for(int i=0; i<=302; i++)
    		for(int j=0; j<=302; j++)
    			time1[i][j]=-1; //先都赋初值为-1 
    	for(int i=1; i<=m; i++)
    	{ 
    		cin>>x>>y>>t;
    		if(t<time1[x][y]||time1[x][y]==-1) //这颗流星到达的时间必须小于前面流星或焦土到达的时间，或者还暂时没有流星及焦土 
    		time1[x][y]=t; 
    		for(int i=0; i<4; i++)
    		{ 
    			nx=x+b1[i],ny=y+b2[i];
    			if(nx>=0&&ny>=0&&(time1[nx][ny]==-1||t<time1[nx][ny])) //注意是 t，不是 t+1 !
    				time1[nx][ny]=t;  //枚举焦土 
    		}
    	}
    	p.x=0,p.y=0,p.time=0,c[0][0]=1;
    	q.push(p);  
    	while(!q.empty())
    	{ 
    		p=q.front();q.pop();
    		for(int i=0; i<4; i++)
    		{ 
    			nx=p.x+b1[i],ny=p.y+b2[i];
    			if(nx>=0&&ny>=0&&c[nx][ny]==0&&(time1[nx][ny]==-1||p.time+1<time1[nx][ny])) //没有流星到过或者bessie到这个格子的时候流星还没有到达 
    			{ 
    				node txt;
    				txt.x=nx,txt.y=ny,txt.time=p.time+1,c[nx][ny]=1; //扩展节点 
    				q.push(txt);
    				if(time1[nx][ny]==-1) //判断当前的格子是否安全 
    				{ 
    					cout<<txt.time<<endl; //输出答案 
    					return 0;
    				}
    			}
    		}
    	}
    	cout<<-1<<endl; //到不了安全的格子就输出-1 
    	return 0;
    }

加了时间的因素，很强

# P2404 自然数的拆分问题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][20200602161716873.png]

#include<bits/stdc++.h> 
    using namespace std;
    int n, p[11]={ 1}, m;
    void print(int a)
    { 
    	for(int i=1; i<a; i++)
    		cout<<p[i]<<"+";
    	cout<<p[a]<<endl;
    }
    void dfs(int a)
    { 
    	for(int i=p[a-1]; i<=m; i++)//回溯后跳出分支
    	{ 
    		if(i==n) return;//防止最后一行输出n
    		p[a]=i;
    		m-=i;
    		if(m==0) print(a);//m减完时，该方案已排列完毕，进行输出
    		else dfs(a+1);//否则继续搜索
    		m+=i;//回溯
    	}
    }
    int main()
    { 
    	cin>>n;
    	m=n;
    	dfs(1);
    	return 0;
    }

又是在 for 循环初始化数组，这种回溯思路（**dfs**）非常难想，包括我现在都还没想懂

# P1596 \[USACO10OCT\]Lake Counting S #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 11]

//第一种方法：BFS
    #include<cstdio>
    #include<queue>
    using namespace std;
    const int maxn = 1e8 + 100;
    struct queue
    { 
        int l = 0,r = 0,a[maxn];
        void push(int x){ 
            a[r++] = x;
        }
        int front(){ 
            return a[l];
        }
        void pop(){ 
            l++;
        }
        int empty(){ 
            return l >= r ? 1 : 0;
        }
    }hori,para;//行的队列 列的队列
    int n,m;
    int ans;
    char s[101][101];
    inline int read(){ //读入优化，可以加快数字的输入
        char p=0;int r=0,o=0;
        for(;p<'0'||p>'9';o|=p=='-',p=getchar());
        for(;p>='0'&&p<='9';r=(r<<1)+(r<<3)+(p^48),p=getchar());
        return o?(~r)+1:r;
    }
    inline void bfs(int x,int y){ //不用递归时可以加inline，提高1ms的运行速度
        s[x][y]='.';
        int dx,dy;
        for(int i=-1;i<=1;i++){ 
            for(int j=-1;j<=1;j++){ 
                dx=x+i;
                dy=y+j;
                if(dx>=0&&dx<n&&dy>=0&&dy<m&&s[dx][dy]=='W'){ 
                    hori.push(dx);
                    para.push(dy);
                }
            }
        }
    }
    int main(){ 
        n=read();m=read();//看不懂的话可以把这一行改成cin或scanf
        for(int i=0;i<n;i++){ 
            scanf("%s",s[i]);
        }
        for(int i=0;i<n;i++){ 
            for(int j=0;j<m;j++){ 
                if(s[i][j]=='W'){ 
                    hori.push(i);
                    para.push(j);
                    while(!hori.empty()){ //如果队列不为空，一个就行了 
                        bfs(hori.front(),para.front());//广搜队列前面的元素
                        hori.pop();para.pop();//弹出元素
                    }
                    ans++;
                }
            }
        }
        printf("%d",ans);
        return 0;
    }
    
    
    //第二种方法：DFS
    #include <bits/stdc++.h>
    using namespace std;
    char a[101][101];
    int ans;
    int n,m;
    void dfs(int x,int y){ 
        a[x][y]='.';
        int dx,dy;
        for(int i=-1;i<=1;i++){ 
            for(int j=-1;j<=1;j++){ 
                dx=x+i;
                dy=y+j;
                if(dx>=0&&dx<=n&&dy>=0&&dy<m&&a[dx][dy]=='W'){ 
                    dfs(dx,dy);
                }
            }
        }
        return;
    }
    int main(){ 
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++){ 
        	scanf("%s",a[i]);//避免换行带来问题这里直接读入字符串
        }
        for(int i=0;i<=n;i++){ 
            for(int j=0;j<m;j++){ 
                if(a[i][j]=='W'){ //如果是W的话就直接开始遍历
                    dfs(i,j);
                    ans++;//水潭加一处
                }
            }
        }
        printf("%d",ans);
        return 0;
    }

**关于此题 BFS：**  
1、双重 for循环代替 dir方向数组  
2、双重 queue存储坐标  
3、手写队列  
4、BFS 不是递归  
5、既然不是递归就加上 inline，可以提高运行速度  
**关于此题 DFS：**  
和 BFS 差不多，就是递不递归的区别

# P1162 填涂颜色 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 12]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 13]

#include <bits/stdc++.h>
    using namespace std;
    int a[32][32],b[32][32];
    int dx[5]={ 0,-1,1,0,0};
    int dy[5]={ 0,0,0,-1,1};//第一个表示不动，是充数的，后面的四个分别是上下左右四个方向
    int n,i,j;
    void dfs(int p,int q){ 
        int i;
        if (p<0||p>n+1||q<0||q>n+1||a[p][q]!=0) return;//如果搜过头或者已经被搜过了或者本来就是墙的就往回
        a[p][q]=1;//染色
        for (i=1;i<=4;i++) dfs(p+dx[i],q+dy[i]);//向四个方向搜索
    }
    int main(){ 
        cin>>n;
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++){ 
                cin>>b[i][j];//其实不拿两个数组也可以，不过我喜欢啦
                if (b[i][j]==0) a[i][j]=0;
                else a[i][j]=2;
            }
        dfs(0,0);//搜索 从0，0开始搜
        for (i=1;i<=n;i++){ 
            for (j=1;j<=n;j++)
            if (a[i][j]==0) cout<<2<<' ';//如果染过色以后i，j那个地方还是0，说明没有搜到，就是周围有墙，当然就是被围住了，然后输出2
            else cout<<b[i][j]<<' ';//因为被染色了，本来没有被围住的水和墙都染成了1，所以就输出b[i][j]
            cout<<'\n';//换行
        }
    }

从边界（0，0）开始搜索，因为与边界连通的块是不闭合的块，输入的块是从（1，1）开始的

# P1032 字串变换 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 15]

#include <iostream>
    #include <string>
    #include <cstring>
    #include <queue>
    #include <map>
    #define maxn 15
    using namespace std;
    struct node{ //方便搜索，也可以使用pair简化
        string str;
        int step;
    }s,v;
    
    string a,b;
    string orginal[maxn];
    string translated[maxn];
    int n,ans;
    map<string,int> ma;//很重要的东西，用来判重，否则会TLE在第3点和第5点
    
    string trans(const string &str,int i,int j){ //最好加上 const 
        string ans = "";
        if (i+orginal[j].length() > str.length())//位置 + 原字符串的长度加大于要转换的字符串 
            return ans;
    
        for (int k=0; k < orginal[j].length();k++)
            if (str[i+k] != orginal[j][k])
                return ans;
    
        ans = str.substr(0,i);
        ans+=translated[j];
        ans+=str.substr(i+orginal[j].length());
        return ans;
    }
    
    void bfs(){ //一个平淡无奇的bfs过程 
        queue <node> q;
        s.str = a;
        s.step = 0;
        q.push(s);
    
        while (!q.empty()){ 
            node u = q.front();
            q.pop();
            string temp;
    
            if(ma[u.str] == 1) //剪枝，判断重复的路径
                continue;
    
            if (u.str == b){ 
                ans = u.step;
                break;
            }
            ma[u.str] = 1;
            for (int i=0;i < u.str.length();i++)//枚举当前串所有可能位置
                for (int j=0; j<n; j++){ //枚举所有可能手段
                    temp = trans(u.str,i,j);
                    if (temp != ""){ 
                        v.str = temp;
                        v.step = u.step+1;
                        q.push(v);
                    }
                }
        }
        if (ans > 10 || ans == 0)
            cout << "NO ANSWER!" << endl;
        else
            cout << ans << endl;
    
    }
    
    int main(){ 
        cin >> a >> b;
        while (cin >> orginal[n] >> translated[n])
            n++;
        bfs();
        return 0;
    }

由题目最小步数，知道要用广搜  
补充：此题代码只能直接上交评测机，不能运行，因为 while 是无穷无尽的

# P1825 \[USACO11OPEN\]Corn Maze S #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 16]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 17]

#include<bits/stdc++.h>
    using namespace std;
    int a[500][500],qx,qy,zx,zy,cz1,cz2,bj[500][500],n,m;
    int d[4][2]= { { -1,0},{ 1,0},{ 0,-1},{ 0,1}};
    struct node
    { 
    	int x;
    	int y;
    	int bs;
    } ans[101010];
    int cz(int x,int y)
    { 
    	for(int i=1; i<=n; i++)
    	{ 
    		for(int j=1; j<=m; j++)
    		{ 
    			if(!(i==x&&j==y))//注意不能与原点相同
    			{ 
    				if(a[i][j]==a[x][y])//直接判断匹配
    				{ 
    					cz1=i;
    					cz2=j;
    					return 0;
    				}
    			}
    		}
    	}
    }
    int bfs()
    { 
    	int head=0,tail=1; //用这个代替了队列 
    	do
    	{ 
    		head++;
    		if(a[ans[head].x][ans[head].y]>='A'&&a[ans[head].x][ans[head].y]<='Z')//判断是不是脚踩传送门
    		{ 
    			cz(ans[head].x,ans[head].y);//找到对应的传送门坐标
    			ans[head].x=cz1;
    			ans[head].y=cz2;
    		}
    		for(int i=0; i<4; i++)
    		{ 
    			int xx=ans[head].x+d[i][0];
    			int yy=ans[head].y+d[i][1];
    			if(a[xx][yy]!=0&&bj[xx][yy]==0)//广搜
    			{ 
    				bj[xx][yy]=1; //不需要回头，故直接标记为 1，此路不再走 
    				tail++;
    				ans[tail].x=xx;
    				ans[tail].y=yy;
    				ans[tail].bs=ans[head].bs+1;
    				if(xx==zx&&yy==zy)//判目标
    				{ 
    					printf("%d\n",ans[tail].bs);
    					return 0;
    				}
    			}
    		}
    	}
    	while(head<tail);
    }
    int main()
    { 
    	char s;
    	scanf("%d%d",&n,&m);
    	for(int i=1; i<=n; i++)
    	{ 
    		for(int j=1; j<=m; j++)
    		{ 
    			cin>>s;//输入预处理，预处理的特别棒 
    			if(s=='.')
    			{ 
    				a[i][j]=1;
    			}
    			if(s>='A'&&s<='Z')
    			{ 
    				a[i][j]=s;//这里是一个很重要的点，等下说明
    			}
    			if(s=='@')
    			{ 
    				qx=i;
    				qy=j;
    				a[i][j]=1;
    			}
    			if(s=='=')
    			{ 
    				zx=i;
    				zy=j;
    				a[i][j]=1;
    			}
    		}
    	}
    	bj[qx][qy]=1;//注意一定要标记起点
    	ans[1].x=qx;
    	ans[1].y=qy;
    	bfs();
    	return 0;
    }

意料之外，情理之中的神奇思路…  
**关于此题 BFS：**  
1、用 tail 和 head 和 数组（加上 **do while** ）代替了队列  
2、BFS 不走回头路（迷宫一类问题）  
3、直接用数字（**ascii** 码）代替了输入的字符

# 支票面额 #

一个采购员去银行兑换一张 y 元 f 分的支票，结果出纳员错给了 f 元 y 分。采购员用去了 n 分之后才发觉有错，于是清点了余额尚有 2y 元 2f 分，问该支票面额是多少？

**输入格式：**  
输入在一行中给出小于100的正整数 n

**输出格式：**  
在一行中按格式 y.f 输出该支票的原始面额。如果无解，则输出 No Solution

**输入样例1：**  
23  
**输出样例1：**  
25.51  
**输入样例2：**  
22  
**输出样例2：**  
No Solution

//第一种方法：枚举
    # include <stdio.h>
    
    int main(void) { 
    	int n, y, f;
    	int i, j;
    	int is=0;
    	
    	scanf ("%d", &n);
    	
    	for(i=0; i<100; i++) { 
    		for (j=0; j<=100; j++) { 
    			if (n == 98*i-199*j) { 
    				f = i;
    				y = j;
    				is = 1;
    				break;
    			}
    		}
    		if (1 == is) break;
    	}
    	
    	if (0 == is) { 
    		printf("No Solution");
    	} else { 
    		printf("%d.%d", y, f);
    	}
    	
    	return 0;
    }
    
    //第二种方法：列表达式
    #include<cstdio>
    #include<iostream>
    using namespace std;
     
    int y,f,n;
     
    int main(){ 
    scanf("%d",&n);
    y=(98-n)/3;
    f=2*y+1;
     
    if((98-n)%3==0) printf("%d.%d\n",y,f);      
    else{ 
        for(int i=0;i<100;i++){ 
            for(int j=0;j<100;j++){ 
                if((2*i*100+2*j)==(j*100+i-n)){ 
                    printf("%d.%d\n",i,j);
                    return 0;
                }
            }
        }
        printf("No Solution\n");
    }
     
    return 0;
    }

第一种方法不解释  
第二种方法：  
首先，按照正常逻辑思维来说，我们会讨论两种情况：

1.y>n 这就意味着，我们可以推出一组方程（两个等式）：

f==2y;

y-n==2f;

但是，很显然，我们可以得到这个方程是负数解，钱不可能是负的，所以（按照正常想法），我们自然可以得出一个结论：y要比n小，也就是第二种情况是必然成立的。

2.y<n 这也意味着，我们可以推出一组方程（两个等式）：

f-1==2y;

100+y-n==2f;

按照正常想法，我们自然可以解出方程：y=(98-n)/3;f=2\*y+1;

所以我会这样写：scanf一个n之后，if（(98-n)%3！=0），那我们就可以直接判断 No solution了，因为钱的单位不管是元还是分，都不可能是小数，必然是整数。然而，然而…

第一个测试点就是不对。

所以，到底错在哪里呢？

这就要回到我们第二种情况最开始的那两个方程，当我们用掉n分之后，所剩下的2y元和2f分真的和最初的钱数有那样的一一对应的关系吗？

并不是，仔细想想平常生活中用现金买东西，我们会发现最后手里剩下的零钱是一大把的，也就是说，在银行给我们钱之后，我们没有花钱之前，我们可以保证，y分的范围一定是小于100的，但是当我们花掉n分钱后，因为在这期间有可能会产生找零的各种情况，我们最后所剩下的2f分钱有可能就是大于100的，举个栗子：n == 97，最开始我们有68元，33分，花掉97分之后，我们剩下66元，136分（我们可以统一到分为单位 验证一下），那么在这种情况里，我们就不能简单地写做：`f-1==2y; 100+y-n==2f;`

不然这会导致看似 No solution，其实是有解的情况。

我猜，这就是第一个测试点卡我的原因。

写代码时候，我们可以直接用两个for循环完事儿，就不用再管（98-n）%3是否为0，但是我觉得代码按照一定逻辑来写也是可以的，虽然看起来冗余了一些。先验证（98-n）%3是否为0，如果为0，直接算出来y和f；如果不为0，再用两个for循环去寻找我们的y和f，也就是暴力搜索。如果这都找不到，那就是 No solution了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200531215037788.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200531215047903.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200601143445539.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200601153129270.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200601171738510.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200601171807243.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200601223047233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200601232106154.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200601232045413.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200602161707320.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[20200602161716873.png]: https://img-blog.csdnimg.cn/20200602161716873.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200602174640699.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200602174654154.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200602201649457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200602201700891.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200602220751114.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200602220803198.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/20200602224123907.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ_size_16_color_FFFFFF_t_70 17]: https://img-blog.csdnimg.cn/20200602224140174.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NvdXJzZXJMaQ==,size_16,color_FFFFFF,t_70