乐趣区

关于数据结构:图论含深搜广搜Red-and-Black最短路径

Red and Black

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

‘.’ – a black tile
‘#’ – a red tile
‘@’ – a man on a black tile(appears exactly once in a data set)
Output
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
Sample Input
6 9
….#.
…..#
……
……
……
……
……
井 @…#
.#..#.
11 9
.#………
.#.#######.
.#.#…..#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#…….#.
.#########.
………..
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..

.

…@…

.

..#.#..
..#.#..
0 0
Sample Output
45
59
6
13

上面是别离用广度优先搜寻和深度优先搜寻的解决方案

//(图论(广搜)) 
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack> 
#include<set> 
#include<vector> 
using namespace std;
struct node{int x,y;// 构造体变量的横纵坐标};
int n,m,ans;// 输出字符图形行数和列数 
char s[25][25];// 字符型邻接矩阵  
int dis[4][2] = {0,1,0,-1,1,0,-1,0};// 挪动 数组,2 个数为一组,模仿横纵坐标变动的过程,如 0,1 示意横坐标不变,纵坐标加 1,即向上挪动 
void bfs(int dx,int dy){
    queue<node>q;
    node start,next;
    start.x = dx;
    start.y = dy;
    s[start.x][start.y] = '#';// 先把终点地位设为 '#' 
    q.push(start);// 将该点入队 
    while(!q.empty()) {start = q.front();// 将队头元素赋值给 start, 以便前面搜寻其相邻元素 
        q.pop();// 队头元素出队 
        for(int i = 0; i < 4; i++){// 遍历该点四个方位邻接点 
            next.x = start.x + dis[i][0];// 进行横纵坐标变动模仿挪动 
            next.y = start.y + dis[i][1];
            if(s[next.x][next.y] == '#'|| next.x > n || next.x <1|| next.y > m ||next.y <1){// 挪动到止境或者 '#' 处返回
//            if(s[next.x][next.y] == '#'|| next.x > n || next.y > m){continue;// 跳过,不再执行后续递归}
            s[next.x][next.y] ='#';// 拜访过就标记为#
            ans++;
            q.push(next); 
        }
        /*for(int dx = -1;dx <= 1;dx++){// 可模仿 8 个方位的挪动变动 
            for(int dy = -1;dy <= 1;dy++)
        }*/
    } 
}
int main(){while(cin >> m >> n,m||n){
        int sx = 0,sy = 0;// 终点的横纵坐标,统计. 的数量的变量
        ans = 1;// 因为其自身也要算上 
        for(int i = 1; i <= n; i++){scanf("%s",s[i] + 1);// 此处一行字符 依照 一个字符串来存 %s, 原本是 s[i], 因为 i 从 1 开始,所以 s[i] 首地址也加 1
            for(int j = 1; j <= m; j++){if(s[i][j] == '@'){// 寻找起始点的地位(横纵坐标)sx = i;
                    sy = j;
                    break; 
                }
            }     
        }
        bfs(sx,sy);// 从终点开始深搜    
        cout << ans << endl;
    } 
    return 0;
} 
//(图论(深搜)) 
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack> 
#include<set> 
#include<vector> 
using namespace std;

int n,m;// 输出字符图形行数和列数 
char s[25][25];// 字符型邻接矩阵 
int sx,sy,ans;// 终点的横纵坐标,统计. 的数量的变量 
int dis[4][2] = {0,1,0,-1,1,0,-1,0};// 挪动 数组,2 个数为一组,模仿横纵坐标变动的过程,如 0,1 示意横坐标不变,纵坐标加 1,即向上挪动 
void dfs(int x,int y){if(s[x][y] =='.'){ans++;}
    s[x][y] = '#';// 找到. 后 把. 置为# 
    int xx,yy;
    for(int i = 0; i < 4; i++){// 遍历该点四个方位邻接点 
        xx = x + dis[i][0];// 进行横纵坐标变动模仿挪动 
        yy = y + dis[i][1];
        if(s[xx][yy] == '#'|| xx > n || xx <1|| yy > m ||yy <1){// 挪动到止境或者 '#' 处返回 
            continue;// 不再执行 dfs 递归 
        }
        dfs(xx,yy);// 递归遍历所有点的四个方向的点 
        /*for(int dx = -1;dx <= 1;dx++){// 可模仿 8 个方位的挪动变动 
            for(int dy = -1;dy <= 1;dy++)
        }*/
    } 
}
int main(){while(cin >> m >> n,m||n){//        if(n==0&&m==0)
//            break;
        ans = 1;// 因为其自身也要算上 
        for(int i = 1; i <= n; i++){scanf("%s",s[i] + 1);// 此处一行字符 依照 一个字符串来存 %s, 原本是 s[i], 因为 i 从 1 开始,所以 s[i] 首地址也加 1
            for(int j = 1; j <= m; j++){if(s[i][j] == '@'){// 寻找起始点的地位(横纵坐标)sx = i;
                    sy = j;
                    break; 
                }
            }     
        }
        dfs(sx,sy);// 从终点开始深搜    
        cout << ans << endl;
    } 
    return 0;
} 

最短门路

在每年的校赛里,所有进入决赛的同学都会取得一件很漂亮的 t -shirt。然而每当咱们的工作人员把上百件的衣服从商店运回到赛场的时候,却是十分累的!所以当初他们想要寻找最短的从商店到赛场的路线,你能够帮忙他们吗?

Input
输出包含多组数据。每组数据第一行是两个整数 N、M(N<=100,M<=10000),N 示意成都的大巷上有几个路口,标号为 1 的路口是商店所在地,标号为 N 的路口是赛场所在地,M 则示意在成都有几条路。N=M= 0 示意输出完结。接下来 M 行,每行包含 3 个整数 A,B,C(1<=A,B<=N,1<=C<=1000), 示意在路口 A 与路口 B 之间有一条路,咱们的工作人员须要 C 分钟的工夫走过这条路。
输出保障至多存在 1 条商店到赛场的路线。
Output
对于每组输出,输入一行,示意工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2

上面别离用 floyed 和图的广度优先算法来解决这一问题

//(floyd 求最短门路(邻接矩阵))
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack> 
#include<set> 
#include<vector> 
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 105;
int a[maxn][maxn];// 邻接矩阵
int n,m;
void floyd(){
    int s = 1;// s 能够定义为为任意一个点 
    for(int i = 1; i <= n; i++){// 每个 j 和 k 通过 i 时都要判断,共有 n 个 i( 两头点) 
        for(int j = 1; j <= n; j++){if(a[i][j] != INF){for(int k = 1; k <= n; k++){if(a[j][i] + a[i][k] < a[j][k]){// 判断一下 j 通过 0,1,2,3,4....n(i) 后到 k 是否比 j -k(间接) 间隔短 
                        a[j][k] = a[j][i] + a[i][k]; 
                    }
                }
            }
        }
    }
    printf("%d\n",a[s][n]);
} 
int main(){while(cin >> n >> m,m || n){memset(a,INF,sizeof(a));
        while(m--){
            int x,y,z;
            cin >> x >> y >> z;
            a[x][y] = a[y][x] = z;
        } 
        floyd();}
    return 0;
}
//(图论(广搜))
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack> 
#include<set> 
#include<vector> 
#define maxn 105
#define INF 0x3f3f3f3f
using namespace std;
int a[maxn][maxn];// 示意两点间隔的邻接矩阵 
bool vis[maxn];// 判断是否被拜访过
int dis[maxn];// 示意两点间隔的数组(用作两头变量)int n,m;// 全局变量,dijkstra() 函数中也要用到 
void dijk(int x,int y){for(int i = 1; i <= y; i++){// 初始化 dis,vis 
        dis[i] = a[x][i];//[1][1] 到 [1][n]
        vis[i] = false;// 所有点都初始化为未拜访过 
    }
    vis[x] = true;// 把第一个值设为已拜访
    int p = 0; 
    for(int i = 1; i <= y; i++){// 为了每次循环都使 minn 复原为 INF 
    int minn = INF;
        for(int j = 1; j <= y; j++){if(vis[j] == 0 && dis[j] < minn){minn = dis[j];// 找到最小的 dis[],即 1 到 1,1 到 2,1 到 3,1 到 4... 中的最小门路 
                p = j;// 把最小门路 (1 到某点)对应的点赋值给 p}
        }
        vis[p] = true;// 把找到的点设为以拜访 
        for(int j = 1; j <= y; j++){// 判断通过 p 点到 j 点的间隔 是否比 间接从 1 点到 j 点的间隔短 
            if(vis[j] == 0 && dis[p] + a[p][j] < dis[j]){// 满足条件就更新 dis[j] 
                dis[j] = dis[p] + a[p][j];
            }
        } 
    } 
}
int main(){while(cin >> n >> m,m||n){
        int x,y,z;
        memset(a,INF,sizeof(a));// 邻接矩阵数组初始化
        while(m--){
            cin >> x >> y >> z;
            a[x][y] = a[y][x] = z;
        }
        dijk(1,n);
        cout << dis[n] << endl;// 输入 1 到最初一个点(此题为 n)的额最短门路 
    } 
    return 0;
} 

退出移动版