分类目录归档:搜索

Dijkstra 最短路径算法

概要

Dijkstra 算法是最常用的求最短路径的算法之一,它同时适用于有向图或无向图。
我们用 w[u][v] 来存储节点 u 到节点 v 的距离(或理解为这条边的权重)。将除源 S 以外的节点分成已标记和未标记的两部分,先更新一次源 S 到相邻节点的距离,然后通过 BFS(广度优先搜索)来遍历所有与未标记的与源 S 间接相连的节点并不断维护从源 S 到 i点的距离 dis[i],最终得到最短路径。这个版本的 Dijkstra 最短路径算法的复杂度约为 O(N^2)。

输入

  • 第 1 行 节点个数 n,边个数 m
  • 第 2~m+1行 边起点 ui,边终点 vi,边权重 w[u][v]

实现

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <cstring>
#define offline
//#include <regex>
#define INF 2147483647
using namespace std;
int main()
{
    //srand((unsigned int)(time(NULL)));
    freopen("Dijkstra.in","r",stdin);
    int n, m, u;//n points,m threads, u as temp source
    scanf("%d%d", &n, &m);
    int w[n][n], d[n];

    bool sign[n];
    memset(sign,0,sizeof(sign));
    sign[0] = 1;
    
    d[0] = 0;
    for (int i = 0; i < n; i++)
        d[i] = INF;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            i == j ? w[i][j] = 0: w[i][j] = INF;

    int t1, t2, t3;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &t1, &t2, &t3);
        w[t1][t2] = t3;
        w[t2][t1] = t3;//only for non-direction map
    }
    //initial for d
    for (int i = 0; i < n; i++)
        d[i] = w[0][i];
    
    
    int min;
    for (int i = 0; i < n; i++)
    {
        min = INF;
        for (int j = 0; j < n; j++)
        {
            if (sign[j] == 0 && d[j] < min)
            {
                min = d[j];
                u = j;
            }
            
        }
        sign[u] = 1;
        for (int v = 0; v < n; v++)
        {
            if ((d[v] > d[u] + w[u][v]) && w[u][v] < INF){
                #ifdef offline
                printf("updated d[%d] from %d to %d\n", v,d[v],d[u]+w[u][v]);
                #endif
                d[v] = d[u] + w[u][v];
            }
        }
    }   
    for (int i = 0; i < n; i++)
        printf("dis[%d] %d\n", i, d[i]);
    return 0;
}

[POJ 2386]Lake Counting

Description

有一个大小为 N × M 的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出
园子里总共有多少水洼?(八连通指的是下图中相对 W 的*的部分)

* * *
* W *
* * *

Input

第 1 行 两个数 N, M
第2~n行 各 M 个数

Sample Input

10 12
W........WW. 
.WWW.....WWW 
....WW...WW. 
.........WW. 
.........W.. 
..W......W.. 
.W.W.....WW. 
W.W.W.....W. 
.W.W......W. 
..W.......W.

Sample Output

3

题解

通过二维布尔表来记录积水,搜索邻接坐标的状态并重置以避免重复计数。

#include "cstdio"
#include "cmath"
#include "cstdlib"
#include "iostream"
#include "cstring"
#define INF 110
#define online
using namespace std;
int count = 0;
int n,m;
bool map[INF][INF];
inline bool handle(int n1,int m1,bool sign)
{
    //endowed W as 1, NULL and * as 0
    //use sign to distinguish the original requestion and derived requestion
    //True->Origin
    if (n1 < 0 || m1 < 0 || n1 >= n || m1 >= m)
    {
        #ifdef debug
        printf("n1 %d m1 %d n %d m %d out\n", n1, m1, n, m);
        #endif
        return 0;
    }
    if (map[n1][m1])
    {
        #ifdef debug
        printf("matched\n");
        #endif
        map[n1][m1] = 0;
        if (sign)
            count++;
        handle(n1,m1-1,0);
        handle(n1,m1+1,0);
        handle(n1+1,m1,0);
        handle(n1-1,m1,0);
        handle(n1-1,m1-1,0);
        handle(n1+1,m1+1,0);
        handle(n1+1,m1-1,0);
        handle(n1-1,m1+1,0);
    }

}

int main()
{
    //initialize
    scanf("%d%d", &n, &m);
    char c, str[m+1];
    memset(map,0,sizeof(map));
    //endowed * as 0, W as 1
    for (int i = 0; i < n; i++)
    {
        scanf("%s", &str);
        for (int j = 0; j < m; j++)
            map[i][j] = str[j] == '.' ? 0 : 1;

    }

    #ifdef debug
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            printf("%d", map[i][j]);
        printf("\n");
    }
    #endif

    //handle
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            handle(i,j,1);
    printf("%d\n", count);

    return 0;
}