HDU 2612 Find a way
//2612 Find a way
//题意:给一幅图，有墙，有KFC，有路。两个人要去KFC约会，有很多个KFC，问两个人去一间KFC总共走的最少步数
//广搜水题，居然被初始化卡了两个钟悲剧了。。。对两个人进行BFS，相加步数即可，在网上看到不少人单独写了两个BFS，用两个单独的二维数组去存步数，可以是可以，但是如果真正理解BFS的话，一个BFS一个二维数组就可以了，没有分开的必要，又节约了50行代码量和200*200*4个字节的空间，O(∩_∩)O~
#include<iostream>
#include<queue>
#define MAXN 0x3fffffff;
using namespace std;
int n, m;
char map[210][210];
int cnt[210][210];
int cnt2[210][210];
int visited[210][210];
int vec[4][2]={{0,1},{-1,0},{1,0},{0,-1}};
struct node
{
int x;
int y;
int step;
bool check()
{
if (x>=0 && x<n && y>=0 && y<m)
return true;
return false;
}
}Y, M;
void BFS(node start, int num)
{
memset(visited, 0, sizeof(visited));
queue<node> Q;
Q.push(start);
visited[start.x][start.y] = true;
while(!Q.empty())
{
node q = Q.front();
Q.pop();
for (int i = 0; i<4; i++)
{
node p = q;
p.x = q.x + vec[i][0];
p.y = q.y + vec[i][1];
p.step ++;
if (p.check() && map[p.x][p.y] != '#' && !visited[p.x][p.y])
{
visited[p.x][p.y] = true;
Q.push(p);
if (map[p.x][p.y] == '@')
{
//BFS精粹
if (num == 1)
cnt[p.x][p.y] = p.step;//第一次
else
cnt[p.x][p.y] += p.step;//第二次
}
}
}
}
}
int main()
{
while (cin>>n>>m)
{
for (int i = 0; i<n; i++)
{
for (int j = 0; j<m; j++)
{
cin>>map[i][j];
if (map[i][j] == 'Y')
{
Y.x = i;
Y.y = j;
Y.step = 0;
}
if (map[i][j] == 'M')
{
M.x = i;
M.y = j;
M.step = 0;
}
}
}
for (i = 0; i<n; i++)
for (int j = 0; j<m; j++)
cnt[i][j] = cnt2[i][j] = MAXN;
BFS(Y, 1);
BFS(M, 2);
int min = MAXN;
for (i = 0; i<n; i++)
{
for (int j = 0; j<m; j++)
{
if (map[i][j] == '@' && (cnt[i][j] < min))
min = cnt[i][j];
}
}
cout<<min * 11<<endl;
}
return 0;
}
//2612 Find a way
//题意:给一幅图，有墙，有KFC，有路。两个人要去KFC约会，有很多个KFC，问两个人去一间KFC总共走的最少步数
//广搜水题，居然被初始化卡了两个钟悲剧了。。。对两个人进行BFS，相加步数即可，在网上看到不少人单独写了两个BFS，用两个单独的二维数组去存步数，可以是可以，但是如果真正理解BFS的话，一个BFS一个二维数组就可以了，没有分开的必要，又节约了50行代码量和200*200*4个字节的空间，O(∩_∩)O~
#include<iostream>
#include<queue>
#define MAXN 0x3fffffff;
using namespace std;
int n, m;
char map[210][210];
int cnt[210][210];
int cnt2[210][210];
int visited[210][210];
int vec[4][2]={{0,1},{-1,0},{1,0},{0,-1}};
struct node
{
int x;
int y;
int step;
bool check()
{
if (x>=0 && x<n && y>=0 && y<m)
return true;
return false;
}
}Y, M;
void BFS(node start, int num)
{
memset(visited, 0, sizeof(visited));
queue<node> Q;
Q.push(start);
visited[start.x][start.y] = true;
while(!Q.empty())
{
node q = Q.front();
Q.pop();
for (int i = 0; i<4; i++)
{
node p = q;
p.x = q.x + vec[i][0];
p.y = q.y + vec[i][1];
p.step ++;
if (p.check() && map[p.x][p.y] != '#' && !visited[p.x][p.y])
{
visited[p.x][p.y] = true;
Q.push(p);
if (map[p.x][p.y] == '@')
{
//BFS精粹
if (num == 1)
cnt[p.x][p.y] = p.step;//第一次
else
cnt[p.x][p.y] += p.step;//第二次
}
}
}
}
}
int main()
{
while (cin>>n>>m)
{
for (int i = 0; i<n; i++)
{
for (int j = 0; j<m; j++)
{
cin>>map[i][j];
if (map[i][j] == 'Y')
{
Y.x = i;
Y.y = j;
Y.step = 0;
}
if (map[i][j] == 'M')
{
M.x = i;
M.y = j;
M.step = 0;
}
}
}
for (i = 0; i<n; i++)
for (int j = 0; j<m; j++)
cnt[i][j] = cnt2[i][j] = MAXN;
BFS(Y, 1);
BFS(M, 2);
int min = MAXN;
for (i = 0; i<n; i++)
{
for (int j = 0; j<m; j++)
{
if (map[i][j] == '@' && (cnt[i][j] < min))
min = cnt[i][j];
}
}
cout<<min * 11<<endl;
}
return 0;
}
补充：软件开发 , C++ ,
