codeforce 192 div2解题报告 - c++编程基础

}
}
if(hang == n)
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
else
{
int lie = 0;
k = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(sp[j][i] == '.')
{
//cout << i << ' ' << j < lie++;
sum[k++] = j+1;
sum[k++] = i+1;
break;
}
}
}
if(lie < n)
printf("-1\n");
else
{
for(int i = 0; i < k-1; i+=2)
printf("%d %d\n", sum[i], sum[i+1]);
}
}

return 0;
}

D. Biridian Forest

题目的意思就是打怪，你站在S点，要前往E点，但是森林中存在怪物，他们也会移动，并且移动的速度和你的一样。你如果到达一个点，这个点也有怪物的话，那你就需要大战怪兽，大战的次数等于怪物的数量。问你最少的大战次数是多少。

由于要求最优路径，肯定要用到BFS，再者，我们需要考虑如何计算我们会不会和怪兽碰上。按照题目意思，只要我们到出口的距离大于怪兽的点到出口的距离，那么我们就会碰到怪兽，这样的话，就直接可以从出口开始，求出各个点到出口的最短距离，再把怪兽的距离和我们的S的距离进行比较，如果小于的话那就不可避免的大战了，额，好吧。就是这样了：

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
char sp[1500][1500];
struct node
{
int x;
int y;
} st,ed;
int vis[1500][1500];
int n, m;
int dx[4] = {0, 0, -1, 1};
int dy[5] = {-1, 1, 0, 0};
bool inmap(node a)
{
if(a.x <0||a.x >= n || a.y<0 || a.y >=m)
return false;
return true;
}

void BFS()
{
memset(vis, -1, sizeof(vis));
queueQ;
vis[ed.x][ed.y] = 0;
Q.push(ed);
node next;
while(!Q.empty())
{
node tp = Q.front();
Q.pop();
for(int i = 0; i < 4; ++i)
{
next.x = tp.x+dx[i];
next.y = tp.y+dy[i];
if(inmap(next) && vis[next.x][next.y]==-1&&sp[next.x][next.y]!='T')
{
vis[next.x][next.y] = vis[tp.x][tp.y]+1;
Q.push(next);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
scanf("%s", sp[i]);
int flag = 0;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(sp[i][j] == 'S')
{
st.x = i;
st.y = j;
if(flag == 1)
{
i = n;
j = m;
}
else
flag = 1;
}
if(sp[i][j] == 'E')
{
ed.x = i;
ed.y = j;
if(flag == 1)
{
i = n;
j = m;
}
else
flag = 1;
}
}
}
BFS();
int cnt = 0;
int MAX = vis[st.x][st.y];
for(int i = 0; i {
for(int j = 0; j < m; ++j)
{
if(sp[i][j]>='1'&& sp[i][j]<='9')
if(vis[i][j] <= MAX && vis[i][j] != -1)
cnt+=(sp[i][j] - '0');
}
}
cout << cnt < return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
char sp[1500][1500];
struct node
{
int x;
int y;
} st,ed;
int vis[1500][1500];
int n, m;
int dx[4] = {0, 0, -1, 1};
int dy[5] = {-1, 1, 0, 0};
bool inmap(node a)
{
if(a.x <0||a.x >= n || a.y<0 || a.y >=m)
return false;
return true;
}

void BFS()
{
memset(vis, -1, sizeof(vis));
queueQ;
vis[ed.x][ed.y] = 0;
Q.push(ed);
node next;
while(!Q.empty())
{

codeforce 192 div2解题报告 (三)