狗狗40题搞完纪念 » 1038

1038
1038.cpp


#include <cstdio>
#include <cstring>

const int MAXN = 128;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

char buf[MAXN][MAXN];
int sx, sy;
bool ans;

bool isyard(int x, int y) {
	return (buf[x - 1][y - 1] != '#' && buf[x - 1][y] != '#' && buf[x][y - 1] != '#')
		|| (buf[x - 1][y + 1] != '#' && buf[x - 1][y] != '#' && buf[x][y + 1] != '#')
		|| (buf[x + 1][y - 1] != '#' && buf[x + 1][y] != '#' && buf[x][y - 1] != '#')
		|| (buf[x + 1][y + 1] != '#' && buf[x + 1][y] != '#' && buf[x][y + 1] != '#');
}

void finddoor(int x, int y) {
	if (buf[x][y] == '.') {
		if ((buf[x - 1][y] == '#' && buf[x + 1][y] == '#') || (buf[x][y - 1] == '#' && buf[x][y + 1] == '#')) {
			sx = x;
			sy = y;
		} else {
			buf[x][y] = '*';
			for (int i = 0; i < 4; ++i) {
				finddoor(x + dx[i], y + dy[i]);
			}
		}
	}
}

void gao(int x, int y, int z) {
	if (buf[x][y] == ' ') {
		ans = true;
	} else if ((buf[x][y] & (1 << z)) == 0) {
		buf[x][y] |= 1 << z;
		// left, forwark, right, back
		z = (z + 2) & 3;
		for (int i = 0; i < 4; ++i) {
			z = (z + 3) & 3;
			if (buf[x + dx[z]][y + dy[z]] != '#') {
				gao(x + dx[z], y + dy[z], z);
				break;
			}
		}
	}
}

int main() {
	int n, m;

	while (scanf("%d%d", &n, &m) != EOF) {
		memset(buf, '#', sizeof(buf));
		for (int i = 1; i <= n; ++i) {
			scanf("%s", buf[i] + 1);
		}
		finddoor(1, 1);
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				if (buf[i][j] == '*') {
					buf[i][j] = '#';
				}
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				if (buf[i][j] == '.') {
					if (isyard(i, j)) {
						buf[i][j] = ' ';
					} else {
						buf[i][j] = '\0';
					}
				}
			}
		}
		ans = false;
		gao(sx, sy, 0);
		puts(ans ? "YES" : "NO");
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//347 	2010-06-29 05:07:49 	Accepted 	1038 	C++ 	10 	196 	anotherpeg 	Source
One Response to “1038”
  1. [...] 有了这几个注意点,基本上AC就没问题了。这题主要是题目理解上的问题了吧,一开始我无论怎样都WA,后来去watashi的blog上一看他的代码,才知道了这些个注意点。然后发现大神的代码写得各种简洁,巧妙的利用了memset对字符串的块刷新和用位运算来表示一个点的四个方向有没有访问过,让我看了各种佩服。不愧是曾经的final冠军~ ?View Code CPP1 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 100 101 102 103 #include<iostream> #include<memory.h> #include<cstdio> using namespace std; int n,m; char map[120][120]; bool vis[120][120][5]; int dir[4][2] = {-1,0,0,1,1,0,0,-1};//上右下左 int fdir[8][2] = {0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1}; int sa,sb,sd;   bool check(int a,int b) { int num1 = 0,num2=0; int ta,tb; for(int i=0;i<4;i++) { ta = a+dir[i][0]; tb = b+dir[i][1]; if(ta>=0&&ta<n&&tb>=0&&tb<m&&map[ta][tb]=='#') { if(i%2)num1++; else num2++; } } if((num1==2&&num2==0)||(num1==0&&num2==2)) { // cout<<num1<<" "<<num2<<" "<<a<<" "<<b<<endl; return true; } return false; }   bool finalfind(int a,int b) { return (a>0&&b>0&&map[a – 1][b – 1] != '#' && map[a – 1][b] != '#' && map[a][b – 1] != '#') || (a>0&&b<m-1&&map[a – 1][b + 1] != '#' && map[a – 1][b] != '#' && map[a][b + 1] != '#') || (a<n-1&&b>0&&map[a + 1][b – 1] != '#' && map[a + 1][b] != '#' && map[a][b – 1] != '#') || (a<n-1&&b<m-1&&map[a + 1][b + 1] != '#' && map[a + 1][b] != '#' && map[a][b + 1] != '#');   }   void dfs(int a,int b,int dirs) { vis[a][b][4]=true; if(check(a,b)) { sa = a; sb = b; sd = dirs; // cout<<a<<" "<<b<<" "<<sd<<endl; return ; } int ta,tb; for(int i=0;i<4;i++) { ta = a+dir[i][0]; tb = b+dir[i][1]; if(ta>=0&&ta<n&&tb>=0&&tb<m&&!vis[ta][tb][4]&&map[ta][tb]=='.') { dfs(ta,tb,i); } } }   bool formal_dfs(int a,int b,int dirs) { vis[a][b][dirs] = true; if(finalfind(a,b)) { //cout<<a<<" "<<b<<endl; return true; } int ta,tb; for(int i=-1;i<3;i++) { ta = a+dir[(4+i+dirs)%4][0]; tb = b+dir[(4+i+dirs)%4][1]; if(ta>=0&&ta<n&&tb>=0&&tb<m&&!vis[ta][tb][4]&& !vis[ta][tb][(4+i+dirs)%4]&&map[ta][tb]=='.') { return formal_dfs(ta,tb,(4+dirs+i)%4); } } return false; }   int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%s",map[i]); memset(vis,0,sizeof(vis)); dfs(0,0,0); //cout<<sa<<" "<<sb<<" "<<sd<<endl; vis[sa][sb][4] = true; if(formal_dfs(sa,sb,sd))printf("YESn"); else printf("NOn"); }   return 0; } [...]

  2.  
Leave a Reply