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