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 0x3f3f3f3fconst 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 0x3f3f3f3fusing 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;}