codeforces edu1 D. Igor In the Museum

2015-12-04 · 2 min read · dfs 记忆化搜索

http://codeforces.com/contest/598/problem/D

题意：给第一个地图。 ‘.’是能走的，‘’是不能走的。**每个‘.’和''之间有一幅画，**给出k个起点，问对于每组起点，最多能观察到多少副画。

思路：dfs.要注意即使只有一个‘*’，从不同方向访问仍然算不同的画。这样就不用标记画是否访问过了。一开始直接暴力dfs..TLE 10

然后发现，如果是在同一个联通快内，能看到的画的最大值是确定的。。如果之前有同一个联通快内的其他点dfs过得到过答案，那么下次就不用再dfs了。。。记得把之前的记过保存下来。。

我具体的写法是把某一次dfs进过的点的恒纵坐标都存起来。。。然后dfs结束后把更新这些沿途中经过的点的答案。。结果还是TLE 10

果然是记忆化写残了。。也不是写残了。。看了几个别人的代码。。。记忆化存的时候是按照某一次来存答案。。而我是按照某个点的坐标。。来存答案。果然还是要提高姿势水平啊。。。SAD

/* ***********************************************
Author :111qqz
Created Time :2015年12月04日 星期五 15时08分22秒
File Name :code/cf/edu1/D.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E3+3;
 7int n,m,k;
 8char maze[N][N];
 9bool pic[N][N];
10int v[N][N];
11int ans[N*N];
12int res;
13int cnt = 0 ;

1bool ok ( int x,int y)
2{
3    if (x>=0&&x<n&&y>=0&&y<m&&v[x][y]==-1)
4	return true;
5    return false;
6}
7int dfs ( int x,int y,int kk)
8{
9    if (!ok(x,y)) return 0;

    if (maze[x][y]=='*') return 1;
    v[x][y] = kk;

    return  dfs(x+1,y,kk)+dfs(x-1,y,kk)+dfs(x,y-1,kk)+dfs(x,y+1,kk);

1}
2int main()
3{
4	#ifndef  ONLINE_JUDGE 
5	freopen("code/in.txt","r",stdin);
6	 #endif

    scanf("%d%d%d",&n,&m,&k);
    for ( int i = 0  ; i < n ; i++) scanf("%s",maze[i]);

1    ms(ans,-1);
2    ms(v,-1);
3    while (k--)
4    {
5	int x,y;
6	scanf("%d %d",&x,&y);

1	x--;
2	y--;
3	if (v[x][y]==-1)
4	    ans[k] = dfs(x,y,k);
5	else ans[k] = ans[v[x][y]];

	printf("%d\n",ans[k]);
	
    
	
    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}