continue;
}
}
return 0;
}
#include
#include
#include
#include
#include
#include
#include
#include
#include
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
bool rr[120],cc[120];
char save[120][120];
vector
vector
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(rr,false,sizeof(rr));
memset(cc,false,sizeof(cc));
for(int i=1;i<=n;i++)
{
row[i].clear();
col[i].clear();
}
for(int i=1;i<=n;i++)
{
scanf("%s",save[i]+1);
for(int j=1;j<=n;j++)
{
if(save[i][j]=='.')
{
rr[i]=true,cc[j]=true; //当前行和列能扫描到
row[i].push_back(j);
col[j].push_back(i);
}
}
}
bool r=true,c=true; //是否所有的行或列能扫描到
for(int i=1;i<=n;i++)
if(!rr[i])
{
r=false;
break;
}
for(int i=1;i<=n;i++)
if(!cc[i])
{
c=false;
break;
}
if(!r&&!c) //行或列都扫描不到
{
printf("-1\n");
continue;
}
if(r) //如果行都能扫描到，直接输出每一行的第一个可以放的位置
{
for(int i=1;i<=n;i++)
printf("%d %d\n",i,row[i][0]);
continue;
}
if(c) //对于列 同理
{
for(int i=1;i<=n;i++)
printf("%d %d\n",col[i][0],i);
continue;
}
}
return 0;
}
D. Biridian Forest
题目意思：
给一个n*m的矩阵，一个起始点和终点，矩阵中的数字表示该位置的魔鬼数量，当从起点到终点选择一条路径时，如果魔鬼能够在人之前或同时到达该路径某一位置，则人和魔鬼要打仗，选择一条路径，使得人与魔鬼打仗的个数最少。
解题思路：
该题主要是思维转换。bfs+贪心
假设人当前选择了一条路径C->D，终点为Ｄ，某处魔鬼B 能够和人C打仗，假设魔鬼在A位置与人打仗，则dis(B,A)<=dis(C,A) =>dis(B,A,D)<=dis(C,D) 如果选择D终点，只需使得Min(dis(B,D))<=dis(C,D) 而dis(B,A,D)>=Min(dis(B,D)) 所以对于某一特定路径，选择终点D打仗比其他任何一点都好。
如果选择从C-D的最短路，则能够打仗的魔鬼数量就最少。
代码：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include