pku 3620簡單搜索
題意：在一塊地里面，干燥的點標記為0，潮濕的點標記為1；求相連的1的最大個數。
由于自己對搜索不太熟悉，當時以為是記憶化搜索，后來用dfs和bfs各寫了一次后，感覺就是一純粹的搜索而已。
我到目前也還覺得，記憶化搜索是DP的一類，搜索過的地方，記錄下來，是要多次用到的。而這個題的搜索，只需簡單的標記一下搜索過的地方，以便不會再搜，而對已搜索的地方進行標記是搜索題的一個共性吧？
當時寫dfs多開了一個數組進行標記，后來看了一下別人的代碼，看到標記數組都不用開，直接在原數組進行標記就得。這樣我才開始思考，記憶化搜索與簡單搜索的不同，記憶化搜索由于要用到搜索過的地方，直接用原數組進行了標記，就無法記錄（也不能太絕對，可能有些情況用記錄值也可以達到標記的效果，這個題貌似也可以，但可能就比較麻煩）。
這個題目用原數組進行標記的話，就要開一個變量統計每一輪搜索的最大值。但這種方法確實是好。
然后用bfs來寫的話，就要用到一個隊列。當時自己寫一個隊列類，調了N久才發現自己錯在一個很低級的理解錯誤上。我定義一個類，類里面有靜態成員，我的目的就是想讓靜態數據成員進行記錄隊列長度。然后又將類像鏈表結構體一樣進行動態分配進行鏈接，還以為那個靜態成員依然是原來那個。
寫出來后發現有很大浪費，主要是由于指針指向沒有認真分析，然后穩健性也非常不好。
干脆用STL的queue算了。
然后又沒有注意同一個點進行了多次進隊，WA一次。
// dfs
/*
#include <iostream>
using namespace std;
int data[101][101],n,m;
bool sgn[101][101];
int main()
{
int dfs(int,int);
int k,i,j,r,c,ans=0;
memset(data,0,sizeof(data));
memset(sgn,0,sizeof(sgn));
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=k;++i)
{
scanf("%d%d",&r,&c);
data[r][c]=1;
}
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
{
dfs(i,j);
ans=ans>data[i][j]?ans:data[i][j];
}
printf("%d\n",ans);
}
int dfs(int i,int j)
{
if(sgn[i][j]) return 0;
if(data[i][j]!=1) return data[i][j];
sgn[i][j]=1;
return data[i][j]+=dfs(i-1,j)+dfs(i,j+1)+dfs(i+1,j)+dfs(i,j-1);
}
*/
//bfs
/*
#include <iostream>
#include <queue>
using namespace std;
int data[101][101],n,m,num;
struct point
{
int x;int y;
};
queue<point> myq;
point conver(int a,int b)
{
point f;f.x=a;f.y=b;return f;
}
void bfs()
{
point s;
while(!myq.empty())
{
s=myq.front();
myq.pop();
if(data[s.x+1][s.y]==1) {myq.push(conver(s.x+1,s.y));data[s.x+1][s.y]=0;}
if(data[s.x][s.y+1]==1) {myq.push(conver(s.x,s.y+1));data[s.x][s.y+1]=0;}
if(data[s.x-1][s.y]==1) {myq.push(conver(s.x-1,s.y));data[s.x-1][s.y]=0;}
if(data[s.x][s.y-1]==1) {myq.push(conver(s.x,s.y-1));data[s.x][s.y-1]=0;}
++num;
}
}
int main()
{
int k,i,j,r,c,max=0;
scanf("%d%d%d",&n,&m,&k);
memset(data,0,sizeof(data));
for(i=1;i<=k;++i)
{
scanf("%d%d",&r,&c);
data[r][c]=1;
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(data[i][j]==1)
{
data[i][j]=0;
myq.push(conver(i,j));
num=0;
bfs();
if(num>max) max=num;
}
printf("%d\n",max);
return 0;
}
*/