小明站在一個矩形房間里，這個房間的地面鋪滿了地磚，每塊地磚的顏色或是紅色或是黑色。小明一開始站在一塊黑色的地磚上，并且小明從一塊地磚可以向上下左右四個方向移動到其他的地磚上，但是他不能移動到紅色地磚上，只能移動到黑色地磚上。
請你編程計算小明可以走到的黑色地磚最多有多少塊。
輸入包含多組測驗資料。
每組輸入首先是兩個正整數W和H，分別表示地磚的列行數。（1<=W，H<=25）
接下來H行，每行包含W個字符，字符含義如下：
‘.’表示黑地磚；
‘#’表示紅地磚；
‘@’表示小明一開始站的位置，此位置是一塊黑地磚，并且這個字符在每組輸入中僅會出現一個。
當W=0，H=0時，輸入結束。
我寫的代碼是
#include<bits/stdc++.h>
using namespace std;
const int maxn=25;
char mpt[maxn][maxn];
int dirt[4][2]={1,0,-1,0,0,1,0,-1};
int vis[maxn][maxn];
struct node{
int x;
int y;
};
queue<node>q;
int bfs(int sx,int sy){
memset(vis,0,sizeof(vis));
node a={sx,sy};
int ans=1;
q.push(a);
vis[sx][sy]=1;
while(!q.empty()){
node b=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=b.x+dirt[i][0];
int ny=b.y+dirt[i][1];
if((mpt[nx][ny]=='@'||mpt[nx][ny]=='.')&vis[nx][ny]==0){
node c={nx,ny};
q.push(c);
vis[nx][ny]=1;
ans++;
}
}
}
return ans;
}
int main(){
int m,n;
while(cin>>m>>n){
if(m==0&n==0){
break;
}
else
memset(mpt,0,sizeof(mpt));
memset(vis,0,sizeof(vis));
while(!q.empty()){
q.pop();
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>mpt[i][j];
}
}
int k,l;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(mpt[i][j]=='@'){
k=i;
l=j;
}
}
}
int ans=bfs(k,l);
cout<<ans<<endl;
}
return 0;
}
有沒有大佬看看問題出在哪里
uj5u.com熱心網友回復：
還是學習一下深度查找演算法吧
那樣做簡單點
uj5u.com熱心網友回復：
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
// 定義狀態
struct Status {
int x;
int y;
};
// 保存地圖
char map[25][25];
// 標志地圖中的每個點是否被訪問過 如果訪問過則為true
bool mark[25][25];
// 四個方向 ----> 上下左右
int go[][2] = {
1,0,
-1,0,
0,1,
0,-1
};
queue<Status>Q;
bool check(int x, int y,int H,int W) {// 檢查位置(x,y) 是否可以訪問
if (x<1 || x>H || y<1 || y>W || mark[x][y] == true || map[x][y] == '#') {
return false;
}
return true;
}
// 使用參考來保存答案
void BFS(int &ret, int H, int W)
{
while (!Q.empty()) {
Status cur = Q.front();
Q.pop();
ret++;
for (int i = 0; i < 4; i++) {// 得到當前位置的下一個位置 有四種可能 即上下左右
int nx = cur.x + go[i][0];// 下一個位置的x坐標
int ny = cur.y + go[i][1];// 下一個位置的y坐標
Status t;// 生成新的狀態
t.x = nx;
t.y = ny;
if (check(nx, ny, H, W)) {// 如果新的狀態符合要求 就入隊
Q.push(t);
mark[nx][ny] = true; // 標記為已經訪問過
}
}
}
}
int main()
{
int W, H;
while (scanf("%d%d", &W, &H) != EOF) {
getchar();//干掉輸入W、H后的那個回車
if (W == 0 && H == 0)break;
// 清空上一次的輸入
for (int i = 0; i < 25; i++) {
for (int j = 0; j < 25; j++) {
mark[i][j] = false;
map[i][j] = 0;
}
}
while (!Q.empty()) {
Q.pop();
}
// 進入本次輸入
for (int i = 1; i <= H; i++) {// 按照每一行直接輸進去
scanf("%s", map[i] + 1);// 注意這里的%s map[i]+1
}
// 初始化
Status head;
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (map[i][j] == '@') {
head.x = i;
head.y = j;
mark[i][j] = true;
}
}
}
Q.push(head);
// ret用來保存答案
int ret = 0;
// 呼叫BFS函式
BFS(ret, H, W);
printf("%d\n", ret);
}
return 0;
}
這個問題在理解了BFS演算法之后就能很快的寫出了，個人感覺BFS和DFS就是狀態之間的轉換，就是從一個狀態轉移到另外一個狀態，所以我首先定義好了狀態，具體的事宜且見上面的代碼。
uj5u.com熱心網友回復：
[/face
。。問題我解決了，是輸入格式要求列行我寫成行列了。。。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/95869.html
標籤：新手樂園
上一篇：DevC++專案編譯時 Makefile.win 報錯
下一篇：矩陣相乘&&判斷輸入格式