1. 电路维修
这道题的话考察最短路径问题，采用dij算法的思想（每次寻找路径中最短的一个点）
说下自己的一些想法，这个题一开始自己想到是BFS，但想不到怎么操作。现在大致的感受就是:像类似于最简单的迷宫问题就最短步数那种，因为每一步距离都为1，所以就BFS搜周围的情况，最后的结果就是Min值。但是这个电路维修这道题，因为顺着电路走和需要改变顺序两种情况用的步数分别是0和1。所以这个情况不同于普通的迷宫问题。 因为这个有可能是0，也有可能是1. 感觉这种权只有0和1的就可以用最短路径可以采取BFS+双端队列来做。 权为0的放入队头，权为1的放入队尾。然后要注意队尾可以入多次，不需要判重，但是队头是需要判重的。
双端队列自己也是第一次接触，然后贴一下代玛吧，方便自己以后看。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int N =505;
char map[N][N];
typedef pair<int , int > PP;
int dis[N][N];
bool st[N][N];
int r,c;
int dx[4]={-1,-1,1,1},dy[4]={-1,1,1,-1};
int ix[4]={-1,-1,0,0},iy[4]={-1,0,0,-1};
int bfs()
{
memset(dis,0x3f,sizeof(dis));//初始化为+无穷
memset(st,0,sizeof(st));//判重数组 每做一个新队列都要重新赋值
char s[]="\\/\\/";
deque <PP> dq;
PP m;m.first=0;m.second =0;
dq.push_back(m);
dis[0][0]=0;
while(dq.size())
{
PP t=dq.front();
dq.pop_front();//用完 就弹出队列
int x=t.first,y=t.second;
if(st[x][y]) continue;//出队只能一次 需要判重
st[x][y]=true;
for(int i=0;i<4;i++)
{
int dirx=x+dx[i],diry=y+dy[i];
int mapx=x+ix[i],mapy=y+iy[i];
if(dirx>=0&&dirx<=r&&diry>=0&&diry<=c)
{
int w=0;
if(map[mapx][mapy]!=s[i]) w=1;//方向不同 则步数加1
if(dis[dirx][diry]>dis[x][y]+w)
{
dis[dirx][diry]=dis[x][y]+w;//dij思想:每次寻找路径最短的一个点（感觉这里是最核心部分）
PP m;m.first=dirx;m.second=diry;
if(w)
{
dq.push_back(m);
}
else dq.push_front(m);
}
}
}
}
if(dis[r][c]==0x3f3f3f3f) return -1; //如果是正无穷 说明 没有走到这里 即没有路
else return dis[r][c];//能走到必然是最小值 因为在for循环扩展点的时候已经加以判断了
}
int main()
{
int T;
cin>>T;
while(T--)
{
scanf("%d%d",&r,&c);
for(int i=0;i<r;i++)
scanf("%s",&map[i]);
int res=bfs();
if(res==-1) printf("NO SOLUTION\n");
else printf("%d\n",res);
}
return 0;
}
2. 小明种草
这个问题是校内模拟赛的一道题。也是用BFS可以解出来。因为队列是先进先出的性质嘛，所以在把草的情况输入之后就可以遍历一遍，然后就把有草的每个点压入队列，并记录一下这个点是第几个月。然后第一次处理的结点自然是初始状态长草的地方，然后用方向向量向四周扩展，如果是空地的话就压入队列，并记录月数为上一个结点+1.然后要记住判重。不过我感觉不用判重也可以吧。假如这个点没长草的话才能把这个点压入队列。不过判重应该还是保险的。。。。然后贴一下代玛：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1005;
char map[N][N];
bool st[N][N];//判重数组
int k,n,m;
struct Grass
{
int x,y,month;
};
void bfs()
{
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
queue<Grass> q;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(map[i][j]=='g')
{
st[i][j]=true;
Grass w;w.x=i;w.y=j;w.month=0;
q.push(w);
}
}
while(q.size())
{
Grass t=q.front();
q.pop();
if(t.month==k) break;
for(int i=0;i<4;i++)
{
int x=t.x+dx[i],y=t.y+dy[i];
if(x>=0&&x<n&&y>=0&&y<m)
{
if(map[x][y]=='.'&&(!st[x][y]))
{
map[x][y]='g';
st[x][y]=true;
Grass v;v.x=x;v.y=y;v.month=t.month+1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",map[i]);
scanf("%d",&k);
bfs();
for (int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%c",map[i][j]);
printf("\n");
}
return 0;
}
3. 乳草的入侵
emm这道题首先有毒的地方是它x,y这个坐标系和平常存数组的方式是反着的，所以要注意调整一下输入。然后初次看这个题和种草还有点像。不过这个题问的是几个月之后可以全长满草。可以用dis数组来存各点离初始点的距离。毕竟每个月向四周长一次草，距离加一就等价于月份加一，然后每次ans=max(ans,dis[i][j])就可以求出最终的月份了。总的来说还是一道中规中矩的BFS，自己还是做的太少了。。QwQ.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct grass
{
int x,y;//k表示第几个星期
}st;
const int N=105;
int X,Y,MX,MY;
char s[N][N];
int d[N][N];//判重 并记录值
const int dx[8]={0,0,-1,1,1,1,-1,-1};
const int dy[8]={-1,1,0,0,1,-1,-1,1};
void bfs()
{
queue<grass> q;
memset(d,-1,sizeof(d));d[st.x][st.y]=0;
q.push(st);int ans=0;
while(q.size())
{
grass t=q.front();q.pop();
for(int i=0;i<8;i++)
{
int x=t.x+dx[i],y=t.y+dy[i];
if(x<1||y<1||x>X||y>Y||s[x][y]=='*')continue;
if(d[x][y]==-1)
{
d[x][y]=d[t.x][t.y]+1;
ans=max(d[x][y],ans);
/*nxt=node(x,y);
q.push(nxt);*/
grass p;p.x=x,p.y=y;
q.push(p);
}
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%d%d%d%d",&Y,&X,&MY,&MX);
st.x=MX;st.y=MY;
for(int i=X;i;i--)scanf("%s",s[i]+1);
bfs();
return 0;
}
4. 矩阵的距离
大意就是求1周围的点矩阵格离1的最短距离就是那个格子的值。那么可以借助dis数组，先将为1的点入队，然后BFS搜一遍，层层扩展，那么扩展到的每个点的距离必然是最短距离（BFS的特性）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=1005;
char map[N][N];
int dis[N][N],n,m;
typedef pair<int ,int >PP;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void bfs()
{
queue<PP> q;
memset(dis,-1,sizeof(dis));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(map[i][j]=='1')
{
dis[i][j]=0;
PP m;m.first=i;m.second=j;
q.push(m);
}
}//初始化符合条件的点入队列 然后开始扩展
while(q.size())
{
PP t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=1&&x<=n&&y>=1&&y<=m&&dis[x][y]==-1)
{
dis[x][y]=dis[t.first][t.second]+1;
PP w;w.first=x,w.second=y;
q.push(w);
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",map[i]+1);
bfs();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",dis[i][j]);
}
printf("\n");
}
return 0;
}
