dfs求解HDU 1312 Red and Black 搜索水題
有一個長方形的房間，上面鋪著方瓷磚，每個貼圖都是紅色或黑色，一個人站在一塊黑瓷磚上，從一個貼圖，他可以移動到四個相鄰貼圖中的一個，但是他不能在紅色的貼圖上移動，只能在黑色的貼圖上移動，
寫一個程式來計算他通過重復上面描述的動作可以達到的黑色方塊的數量，
輸入
輸入由多個資料集組成，資料集以包含兩個正整數W和H的一行開始;W和H分別為x方向和y方向的瓦片數量，W和H不超過20，
資料集中共有H行，每行包含W個字符，每個字符都表示一個貼圖的顏色，如下所示，
”，——一塊黑色的瓷磚
“#”——一個紅色的貼圖
“@”——一個躺在黑色瓷磚上的人(在資料集中只出現一次)
輸出
對于每個資料集，你的程式應該輸出一行，其中包含他從初始貼圖(包括自己)可以到達的貼圖的數量，
題目大意，從標識為@的點開始標識為’ . '的地方可以走的通，而@的地方被攔截，問整個地圖可走的長度，
AC代碼如下
#include<stdio.h>
#include<string.h>
int w,h;//輸入地圖的大小
char m[25][25];//地圖大小
int stax,stay;//開始探索的起始,stax,stay
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//對該點進行上下左右四個點方向探索
int sum=0;
void dfs(int x, int y)
{
int i,j;
int x1,y1;
for(i=0;i<4;i++)
{
x1=x+dx[i];
y1=y+dy[i];//下左右依次移動
if(m[x1][y1]=='.'&&x>0&&x<=h&&y>0&&y<=w)
{
sum++;
m[x1][y1]='#';//探索后變為#防止二次搜索
dfs(x1,y1);//重復探索
}
}
}
int main()
{
int i,j;
while(scanf("%d%d",&w,&h)&&w!=0&&h!=0)
{
getchar();//吸識訓車
sum=0;
memset(m, 0, sizeof(m));
for(i=1;i<=h;i++)//輸入地圖并標記起點
{
for(j=1;j<=w;j++)
{
scanf("%c", &m[i][j]);
if(m[i][j]=='@')
{
stax=i;
stay=j;
m[i][j]='#';//起點算一個'.',標記后將它變成#
}
}
getchar();
}
dfs(stax,stay);
printf("%d\n", sum+1);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253010.html
標籤：其他
上一篇：條件控制陳述句以及案例
下一篇：初來乍到 自我介紹