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;
}
发表回复