公司的程序员不够用了，决定把产品经理都转变为程序员以解决开发时间长的问题。
在给定的矩形网格中，每个单元格可以有以下三个值之一：
值0代表空单元格;
值1代表产品经理;
值2代表程序员;
每分钟，任何与程序员(在4个正方向上)相邻的产品经理都会变成程序员。
返回直到单元格中没有产品经理为止所必须经过的最小分钟数。
如果不可能，返回-1。
以下是一个4分钟转变完成的示例：
2 1 1 2 2 1 2 2 2 2 2 2 2 2 2
1 1 0 -> 2 1 0 -> 2 2 0 -> 2 2 0 -> 2 2 0
0 1 1 0 1 1 0 1 1 0 2 1 0 2 2
输入格式
不固定多行（行数不超过10），毎行是按照空格分割的数字(不固定，毎行数字个数不超过10)。
其中每个数组项的取值仅为0、1、2三种。
读取时可以按行读取，直到读取到空行为止，再对读取的所有行做转换处理。
输出格式
如果能够将所有产品经理变成程序员，则输出最小的分钟数。
如果不能够将所有的产品经理变成程序员，则返回-1.
输入样例1：
0 2
1 0
输出样例1：
-1
输入样例2：
1 2 1
1 1 0
0 1 1
输出样例2：
3
输入样例3：
1 2
2 1
1 2
0 1
0 1
1 1
输出样例3：
4
思路分析：
1.dfs方法
读取输入的时候用一个变量numof1记录数组中1的个数，每次dfs到满足条件的1的时候numof1--，最后通过判断numof1==0来判断是否有等于1的节点不能被变为2。
用一个tmp数组和a数组，因为如果在原来数组上将1变为2，那么接下来遍历到的时候，会把新2继续更改它周围为1的节点。
不符合我们一次遍历的条件。需要用tmp来记录上一次的数组，用a记录一次遍历的数组结果，遍历完执行tmp=a。
在复制a到tmp的过程中，可以判断tmp和a是否一致，如果数组元素都一致，则break。
代码如下：
include<iostream>
include<vector>
using namespace std;
const int N=12;
int a[N][N],tmp[N][N];
int index,index1,numof1;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int curx=x+dx[i];
int cury=y+dy[i];
if(curx>=0&&curx<=index&&cury>=0&&cury<=index1&&a[curx][cury]==1)
{
a[curx][cury]=2;
numof1--;
}
}
}
int main()
{
string str;
while(getline(cin,str))
{
++index;
index1=0;
for(int i=0;i<str.size();)
{
int t=0;
while(i<str.size()&&str[i]!=' ')
{
t=t*10+str[i]-'0';
i++;
}
if(t==1)
numof1++;
a[index][++index1]=t;
i++;
}
}
int res=0;
for(int i=1;i<=index;i++)
{
for(int j=1;j<=index1;j++)
{
tmp[i][j]=a[i][j];
}
}
while(numof1)
{
res++;
for(int i=1;i<=index;i++)
for(int j=1;j<=index1;j++)
{
if(tmp[i][j]==2)
{
// cout<<i<< " "<<res<<" "<<j<<endl;
dfs(i,j);
}
}
int flag=1;
for(int i=1;i<=index;i++)
{
for(int j=1;j<=index1;j++)
{
if(tmp[i][j]!=a[i][j])
{
tmp[i][j]=a[i][j];
flag=0;
}
}
}
if(flag==1)
{
cout<<-1<<endl;
break;
}
}
if(numof1==0)
cout<<res<<endl;
}
2.bfs办法
多源最短路问题
用一个新的数组维持结果，bfs相当于按层遍历，每次遍历节点值为2的相邻节点。
第一次遍历原数组中为2的节点，然后把遍历到的满足条件的放入队列，下一次再遍历。
队列中进入过的元素可能如下：
0 0 0 0 1 1 1 1 2 2 3 4 依次递增
代码如下：
include<iostream>
include<algorithm>
include<queue>
include<sstream>
include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=12;
int a[N][N],dist[N][N];
int n,m;
int bfs()
{
queue<PII> que;
memset(dist,-1,sizeof dist);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(a[i][j]==2)
{
dist[i][j]=0;
que.push({i,j});
}
}
while(!que.empty())
{
auto cur=que.front();
que.pop();
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
for(int i=0;i<4;i++)
{
int x=cur.first+dx[i];
int y=cur.second+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&a[x][y]==1&&dist[x][y]==-1)
{
// a[x][y]=2;
dist[x][y]=dist[cur.first][cur.second]+1;
que.push({x,y});
}
}
}
int res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]==1&&dist[i][j]==-1)
return -1;
res=max(res,dist[i][j]);
}
}
return res;
}
int main()
{
string line;
while(getline(cin,line))
{
int k=0;
stringstream ssin(line);
while(ssin>>a[n][k]) k++;
m=k;
n++;
}
cout<<bfs()<<endl;
return 0;
}
