使用BFS的最短距离

我正在尝试解决this SPOJ problem。该问题要求找到每个黑色（1）像素的最短路径。使用BFS的最短距离

由于它是一个未加权的图，所以我使用了BFS。

输入：

它给：的

323 
434 
343

代替：

101 
212 
323

这是我的代码

#include<iostream> 
#include<queue> 
#include<string.h> 
using namespace std; 
typedef pair < int, int >ii; 
int R, C, i, j; 
queue <ii> myQueue; 

int visit[100][100]; 
int dist[100][100]; 
void bfs(ii s) 
{ 
    int i, j; 
    int count = 0; 
    ii node; 
    memset(visit, 0, sizeof(visit)); 
    memset(dist, 0, sizeof(dist)); 
    myQueue.push(s); 
    dist[node.first][node.second] = 0; 

    while (!myQueue.empty()) { 
     node = myQueue.front(); 
     myQueue.pop(); 
     if (visit[node.first][node.second]) 
      continue; 
     visit[node.first][node.second] = 1; 

     //cout << node.first << " " << node.second << "\n"; 
     i = node.first; 
     j = node.second; 

     if (j - 1 < R && j - 1 >= 0) { 
      myQueue.push(make_pair(i, j - 1)); 
      if(dist[i][j - 1] == 0) 
      dist[i][j - 1] = dist[i][j] + 1; 
     } 
     if (j + 1 < R && j + 1 >= 0) { 
      myQueue.push(make_pair(i, j + 1)); 
      if(dist[i][j+1] == 0) 
      dist[i][j + 1] = dist[i][j] + 1; 
     } 
     if (i - 1 < C && i - 1 >= 0) { 
      myQueue.push(make_pair(i - 1, j)); 
      if(dist[i-1][j] == 0) 
      dist[i - 1][j] = dist[i][j] + 1; 
     } 
     if (i + 1 < C && i + 1 >= 0) { 
      myQueue.push(make_pair(i + 1, j)); 
      if(dist[i+1][j] == 0) 
      dist[i + 1][j] = dist[i][j] + 1; 
     } 
    } 
} 

int main() 
{ 
    char input[100][100]; 
    scanf("%d %d", &R, &C); 
    for (i = 0; i < R; i++) 
     scanf("%s", &input[i]); 
    int GRID[R][C]; 
    for (i = 0; i < R; i++) 
     for (j = 0; j < C; j++) 
      GRID[i][j] = input[i][j] - '0'; 
    for (i = 0; i < R; i++) 
     for (j = 0; j < C; j++) { 
      if (GRID[i][j] == 1) 
       bfs(make_pair(i, j)); 
     } 
    for (i = 0; i < R; i++) { 
     for (j = 0; j < C; j++) { 
      printf("%d", dist[i][j]); 
     } 
     printf("\n"); 
    } 
}

ideone

来源

2012-06-20 ka4tik

请发布问题本身 - 而不仅仅是它的链接。此外，除了链接到完整的代码之外，还要发布可疑的代码部分。 – amit

试试这个：

if (j - 1 < R && j - 1 >= 0) { 
    myQueue.push(make_pair(i, j - 1)); 
    if(dist[i][j - 1] == 0) 
    dist[i][j - 1] = dist[i][j] + 1; 
}

所有DIST [] []做到这一点。

来源

2012-06-20 10:04:28

您已经加倍结果可能是因为您在成对顶点之间运行了两次BFS。

但我不确定。

来源

2012-06-20 10:08:01

使用BFS的最短距离

回答

相关问题