Posted on 2012-01-15 17:53
C小加 閱讀(583)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
簡單DFS，數(shù)據(jù)很弱。。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char map[23][23];
typedef struct
{
int x,y;
int flag;
}point;
point p[5];
int _max[5];
int _num[5];
int flag;
void door();
void dfs(int x,int y)
{
if(map[x][y]!='X')
{
switch(map[x][y])
{
case 'a': _num[0]++;break;
case 'b': _num[1]++;break;
case 'c': _num[2]++;break;
case 'd': _num[3]++;break;
case 'e': _num[4]++;break;
case 'A': {p[0].x=x;p[0].y=y;p[0].flag++;return;}
case 'B': {p[1].x=x;p[1].y=y;p[1].flag++;return;}
case 'C': {p[2].x=x;p[2].y=y;p[2].flag++;return;}
case 'D': {p[3].x=x;p[3].y=y;p[3].flag++;return;}
case 'E': {p[4].x=x;p[4].y=y;p[4].flag++;return;}
case 'G': {flag=1;return;}
}
map[x][y]='X';//說明此路已走過
dfs(x-1,y);
dfs(x,y+1);
dfs(x+1,y);
dfs(x,y-1);
door();
}
}
//如果鑰匙夠了就打開這扇門
void door()
{
for(int i=0;i<5;i++)
{
if(p[i].flag)
{
if(_num[i]==_max[i])
{
map[p[i].x][p[i].y]='X';
dfs(p[i].x-1,p[i].y);
dfs(p[i].x,p[i].y+1);
dfs(p[i].x+1,p[i].y);
dfs(p[i].x,p[i].y-1);
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
int m,n;
int sx,sy;
while(cin>>m>>n,m+n)
{
//初始化
flag=0;
memset(_max,0,sizeof(_max));
memset(_num,0,sizeof(_num));
memset(p,0,sizeof(p));
memset(map,'X',sizeof(map));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>map[i][j];
if(map[i][j]=='S') {sx=i;sy=j;}//入口
//初始化最大鑰匙數(shù)量
else if(map[i][j]=='a') _max[0]++;
else if(map[i][j]=='b') _max[1]++;
else if(map[i][j]=='c') _max[2]++;
else if(map[i][j]=='d') _max[3]++;
else if(map[i][j]=='e') _max[4]++;
}
}
dfs(sx,sy);
door();
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}