Input
Output
Sample Input
2 3 3 ### #.# ### 7 6 ####### #.#.### #.#.### #.#.#.# #.....# #######
Sample Output
Maximum rope length is 0. Maximum rope length is 8.
Hint
AC代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int c,r,dx,dy;
int ans;
char a[1005][1005];
int b[1005][1005];
int mx[4] = {0,0,1,-1};
int my[4] = {1,-1,0,0};
void dfs(int x,int y,int t)
{
b[x][y]=1;
if(ans<t)
{
dx=x;
dy=y;
ans=t;
}
int xx,yy,i;
for(i=0;i<4;i++)
{
xx=x+mx[i];
yy=y+my[i];
if(xx>-1&&xx<r&&yy>-1&&yy<c&&!b[xx][yy]&&a[xx][yy]!=‘#‘)
dfs(xx,yy,t+1);
}
b[x][y]=1;
}
int main()
{
int t,i,j,sx,sy;
scanf("%d",&t);
while(t--)
{
int l=0;
ans=0;
memset(b,0,sizeof(b));
scanf("%d %d",&c,&r);
for(i=0;i<r;i++)
{
scanf("%s",a[i]);
for(j=0;j<c&&l==0;j++)
if(a[i][j]==‘.‘)
{
l=1;
sx=i;
sy=j;
}
}
dfs(sx,sy,0);
memset(b,0,sizeof(b));
dfs(dx,dy,0);
printf("Maximum rope length is %d.\n",ans);
}
}
我的代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 6 using namespace std; 7 8 int r, c; 9 char a[1005][1005]; 10 int num[1005][1005]; 11 int n_step, max_step, nx, ny; 12 int dx[4] = {0, 1, 0, -1}; 13 int dy[4] = {1, 0, -1, 0}; 14 15 int dfs(int x, int y, int step) 16 { 17 n_step = step; 18 a[x][y] = ‘#‘; 19 for(int i = -1; i <= 1; i++) 20 { 21 22 max_step = max(max_step, n_step); 23 nx = x + dx[i]; 24 ny = y + dy[i]; 25 if(nx > 0 && nx <= r && ny > 0 && ny <= c && a[nx][ny] == ‘.‘) 26 { 27 n_step++; 28 dfs(nx, ny, n_step); 29 } 30 } 31 return max_step; 32 } 33 34 int main() 35 { 36 int t; 37 38 scanf("%d", &t); 39 while(t--) 40 { 41 n_step = 0; 42 max_step = 0; 43 scanf("%d %d", &r, &c); 44 getchar(); 45 memset(num, 0, sizeof(num)); 46 for(int i = 0; i < max(r, c) + 1; i++) 47 { 48 a[0][i] = ‘#‘; 49 a[i][0] = ‘#‘; 50 a[r+1][i] = ‘#‘; 51 a[i][c+1] = ‘#‘; 52 } 53 54 //cout << r << c <<endl; 55 for(int i = 1; i <= r; i++) 56 { 57 for(int j = 1; j <= c; j++) 58 { 59 scanf("%c", &a[i][j]); 60 } 61 getchar(); 62 } 63 64 for(int i = 1; i <= r; i++) 65 { 66 for(int j = 1; j <= c; j++) 67 { 68 if(a[i][j] == ‘.‘) 69 { 70 //cout << "++" << i << j << endl; 71 int ans = dfs(i, j, 0); 72 printf("%d\n", ans); 73 break; 74 } 75 } 76 } 77 78 79 } 80 return 0; 81 }
原文：https://www.cnblogs.com/ruruozhenhao/p/8886456.html
