邱老師降臨小行星

Time Limit: 20 Sec??Memory Limit: 256 MB

題目連接

http://acm.uestc.edu.cn/#/contest/show/61

Description

人贏邱老師和任何男生比，都是不虛的。有一天，邱老師帶妹子(們)來到了一個N行M列平面的小行星。對于每一個著陸地點(diǎn)，邱老師總喜歡帶著妹子這樣走：假設(shè)著陸地點(diǎn)為(r0,?c0)，那么他們下一步只能選擇相鄰格點(diǎn)，向四周走，即(r0–1,?c0),?(r0?+?1,?c0),?(r0,?c0–1)或(r0,?c0?+?1)。之后的路程必須嚴(yán)格按照右轉(zhuǎn)-前進(jìn)-左轉(zhuǎn)-前進(jìn)-右轉(zhuǎn)......的道路前行。但是由于邱老師很心疼妹子，所以崎嶇的山脈不可以到達(dá)。當(dāng)不能前進(jìn)時必須要原路返回。如下圖。

問，邱老師在哪里著陸可以游歷這顆星球最多的土地，輸出可能訪問到的最多的格點(diǎn)數(shù)。

Input

第一行一個整數(shù)T, 0<T≤20，表示輸入數(shù)據(jù)的組數(shù)。 對于每組數(shù)據(jù)，第一行有兩個整數(shù)N和M，分別表示行數(shù)和列數(shù)，0<N,M≤1000 下面N行，每行M個字符(0或1)。 1代表可到達(dá)的地方，0代表山脈(不可到達(dá)的地方)。

Output

對于每一組數(shù)據(jù)，輸出一個整數(shù)后換行，表示選擇某點(diǎn)著陸后，可能訪問到的最多的格點(diǎn)數(shù)。

?

Sample Input

2
4 3
111
111
111
111
3 3
111
101
111

Sample Output

10
4

HINT

?

題意

?

題解：

記憶化搜索，存一下值就好了

代碼：

?

//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 200001 #define mod 10007 #define eps 1e-9 int Num; char CH[20]; //const int inf=0x7fffffff; //нчоч╢С const int inf=0x3f3f3f3f; /*inline void P(int x) {Num=0;if(!x){putchar('0');puts("");return;}while(x>0)CH[++Num]=x%10,x/=10;while(Num)putchar(CH[Num--]+48);puts(""); } */ //************************************************************************************** inline ll read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } inline void P(int x) {Num=0;if(!x){putchar('0');puts("");return;}while(x>0)CH[++Num]=x%10,x/=10;while(Num)putchar(CH[Num--]+48);puts(""); }char s[1001][1001]; int dp[1001][1001][8]; int dx[8]={-1,0,0,1,1,0,0,-1}; int dy[8]={0,1,1,0,0,-1,-1,0}; int n,m; void dfs(int i,int j,int k) {if(k%2==0){if(i+dx[k]<0||i+dx[k]>=n||j+dy[k]<0||j+dy[k]>=m)dp[i][j][k]=0;else if(s[i+dx[k]][j+dy[k]]=='0')dp[i][j][k]=0;else{if(dp[i+dx[k]][j+dy[k]][k+1]==-1)dfs(i+dx[k],j+dy[k],k+1);dp[i][j][k]=1;dp[i][j][k]+=dp[i+dx[k]][j+dy[k]][k+1];}}else{if(i+dx[k]<0||i+dx[k]>=n||j+dy[k]<0||j+dy[k]>=m)dp[i][j][k]=0;else if(s[i+dx[k]][j+dy[k]]=='0')dp[i][j][k]=0;else{if(dp[i+dx[k]][j+dy[k]][k-1]==-1)dfs(i+dx[k],j+dy[k],k-1);dp[i][j][k]=1;dp[i][j][k]+=dp[i+dx[k]][j+dy[k]][k-1];}} } int main() {int t=read();for(int cas=1;cas<=t;cas++){n=read(),m=read();for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<8;k++)dp[i][j][k]=-1;for(int i=0;i<n;i++)scanf("%s",s[i]);int ans2=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='0')continue;int ans=1;if(dp[i][j][0]==-1)dfs(i,j,0);ans+=dp[i][j][0];if(dp[i][j][2]==-1)dfs(i,j,2);ans+=dp[i][j][2];if(dp[i][j][4]==-1)dfs(i,j,4);ans+=dp[i][j][4];if(dp[i][j][6]==-1)dfs(i,j,6);ans+=dp[i][j][6];ans2=max(ans2,ans);}}printf("%d\n",ans2);} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qscqesze/p/4489779.html

總結(jié)

以上是生活随笔為你收集整理的2015 UESTC 搜索专题B题 邱老师降临小行星 记忆化搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。