cf-Round542-Div2-C（暴力+DFS）

题目链接：http://codeforces.com/contest/1130/problem/C

思路：

利用DFS搜索(r1,c1)和(r2,c2)可到达的点的集合，分别存在a1，a2中，若a1=a2，即从(r1,c2)可直接到达(r2,c2)，输出0即可。否则，暴力枚举a1，a2即可，找到最小值即最终答案。我在做的时候没看清数据大小把a1，a2的大小开小了，然后wa了一发。时间复杂度为O(n^4)。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct node{
 5     int r,c;
 6 }a1[2505],a2[2505];
 7 
 8 int n,r1,c1,r2,c2;
 9 char a[55][55];
10 int go[4][2]={-1,0,0,1,1,0,0,-1};
11 
12 void dfs(int x,int y,char c){
13     for(int i=0;i<4;++i){
14         int xx=x+go[i][0],yy=y+go[i][1];
15         if(xx>=0&&xx<n&&yy>=0&&yy<n&&a[xx][yy]=='0'){
16             a[xx][yy]=c;
17             dfs(xx,yy,c);
18         }
19     }
20 }
21 
22 int main(){
23     scanf("%d",&n);
24     scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
25     for(int i=0;i<n;++i)
26         scanf("%s",a[i]);
27     --r1,--c1,--r2,--c2;
28     a[r1][c1]='2';
29     dfs(r1,c1,'2');
30     if(a[r2][c2]=='2'){
31         printf("0
");
32         return 0;
33     }
34     a[r2][c2]='3';
35     dfs(r2,c2,'3');
36     int p1=0,p2=0;
37     for(int i=0;i<n;++i)
38         for(int j=0;j<n;++j){
39             if(a[i][j]=='2') a1[p1].r=i,a1[p1++].c=j;
40             if(a[i][j]=='3') a2[p2].r=i,a2[p2++].c=j;
41         }
42     int res=0x3f3f3f3f;
43     for(int i=0;i<p1;++i)
44         for(int j=0;j<p2;++j){
45             int tmp=(a1[i].r-a2[j].r)*(a1[i].r-a2[j].r)+(a1[i].c-a2[j].c)*(a1[i].c-a2[j].c);
46             if(tmp<res) res=tmp;
47         }
48     printf("%d
",res);
49     return 0;
50 }