01迷宫
題目描述
有一個僅由數字0與1組成的n×n格迷宮。若你位于一格0上，那么你可以移動到相鄰4格中的某一格1上，同樣若你位于一格1上，那么你可以移動到相鄰4格中的某一格0上。
你的任務是：對于給定的迷宮，詢問從某一格開始能移動到多少個格子（包含自身）。
輸入輸出格式
輸入格式：
輸入的第1行為兩個正整數n，m。
下面n行，每行n個字符，字符只可能是0或者1，字符之間沒有空格。
接下來m行，每行2個用空格分隔的正整數i,j，對應了迷宮中第i行第j列的一個格子，詢問從這一格開始能移動到多少格。
輸出格式：
輸出包括m行，對于每個詢問輸出相應答案。
輸入輸出樣例
輸入樣例#1：
2 2
01
10
1 1
2 2
輸出樣例#1：
4
4
說明
所有格子互相可達。
對于20%的數據，n≤10；
對于40%的數據，n≤50；
對于50%的數據，m≤5；
對于60%的數據，n≤100，m≤100；
對于100%的數據，n≤1000，m≤100000。
.
.
.
.
.
.
.
分析
由于每次只向四個方向嘗試移動，所以可采用深搜。
然而數據規模中，n<=1000，m<=100000，如果每次輸入坐標時重新走一次將會超時。
再想想，每一次搜索會找到一個區塊，該區塊中所有點的答案都相同，所以，答案可以存在一個數組里
題目每給出一個坐標，先判斷該坐標是否已有答案（通過前面已給出的點搜索獲得的），是則直接輸出，否則深搜：先重置pl，為了將該點所屬區塊都染上色（不能在深搜內部染色，因為過程中并不知道區域內到底有多少連通點），在一趟深搜過程中，每到一個新的點就pl+1，并將該點的坐標存在臨時數組里，搜索結束后再依據坐標數組把答案數組的對應位置填上pl。
.
.
.
.
.
.
.
.
程序：
const x1:array[1..4]of longint=(1,-1,0,0); y1:array[1..4]of longint=(0,0,1,-1); var a,ans:array[0..1001,0..1001]of longint; x,y:array[0..1000001]of longint; n,m,pl,i,j:longint; ch:char;procedure dfs(p,q:longint); var i,u,v:longint; begininc(pl);x[pl]:=p;y[pl]:=q;ans[p,q]:=1;for i:=1 to 4 dobeginu:=p+x1[i];v:=q+y1[i];if (u<1)or(u>n)or(v<1)or(v>n) then continue;if (ans[u,v]>0) then continue;if (a[u,v]=a[p,q]) then continue;dfs(u,v);end; end;beginfillchar(ans,sizeof(ans),0);readln(n,m);for i:=1 to n dobeginfor j:=1 to n dobeginread(ch);a[i,j]:=ord(ch)-ord('0');end;readln;end;for i:=1 to m dobeginpl:=0;readln(x[i],y[i]);if ans[x[i],y[i]]>0 thenbeginwriteln(ans[x[i],y[i]]);continue;end;dfs(x[i],y[i]);for j:=1 to pl doans[x[j],y[j]]:=pl;writeln(pl);end; end.轉載于:https://www.cnblogs.com/YYC-0304/p/9499995.html
總結
