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;
}