codeforces edu1 D. Igor In the Museum
http://codeforces.com/contest/598/problem/D
题意：给第一个地图。 ‘.’是能走的，‘’是不能走的。**每个‘.’和’‘之间有一幅画，**给出k个起点，问对于每组起点，最多能观察到多少副画。
思路：dfs.要注意即使只有一个‘*’，从不同方向访问仍然算不同的画。这样就不用标记画是否访问过了。一开始直接暴力dfs..TLE 10
然后发现，如果是在同一个联通快内，能看到的画的最大值是确定的。。如果之前有同一个联通快内的其他点dfs过得到过答案，那么下次就不用再dfs了。。。记得把之前的记过保存下来。。
我具体的写法是把某一次dfs进过的点的恒纵坐标都存起来。。。然后dfs结束后把更新这些沿途中经过的点的答案。。结果还是TLE 10
果然是记忆化写残了。。也不是写残了。。看了几个别人的代码。。。记忆化存的时候是按照某一次来存答案。。而我是按照某个点的坐标。。来存答案。果然还是要提高姿势水平啊。。。SAD
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月04日 星期五 15时08分22秒
4File Name :code/cf/edu1/D.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25
26
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E3+3;
34int n,m,k;
35char maze[N][N];
36bool pic[N][N];
37int v[N][N];
38int ans[N*N];
39int res;
40int cnt = 0 ;
41
42bool ok ( int x,int y)
43{
44 if (x>=0&&x<n&&y>=0&&y<m&&v[x][y]==-1)
45 return true;
46 return false;
47}
48int dfs ( int x,int y,int kk)
49{
50 if (!ok(x,y)) return 0;
51
52 if (maze[x][y]=='*') return 1;
53 v[x][y] = kk;
54
55 return dfs(x+1,y,kk)+dfs(x-1,y,kk)+dfs(x,y-1,kk)+dfs(x,y+1,kk);
56
57
58}
59int main()
60{
61 #ifndef ONLINE_JUDGE
62 freopen("code/in.txt","r",stdin);
63 #endif
64
65 scanf("%d%d%d",&n,&m,&k);
66 for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
67
68 ms(ans,-1);
69 ms(v,-1);
70 while (k--)
71 {
72 int x,y;
73 scanf("%d %d",&x,&y);
74
75 x--;
76 y--;
77 if (v[x][y]==-1)
78 ans[k] = dfs(x,y,k);
79 else ans[k] = ans[v[x][y]];
80
81 printf("%d\n",ans[k]);
82
83
84
85 }
86
87
88 #ifndef ONLINE_JUDGE
89 fclose(stdin);
90 #endif
91 return 0;
92}