模拟栈做法.txt

HDUOJ_ACM题目集合~~希望各位能用得上

#include<iostream>
#include<stack>
using namespace std;
#define MAXN 9
int n,m,t;
char map[MAXN][MAXN];
bool success;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
class point{
public:
  int x;
  int y;
  int t;
  char maze[MAXN][MAXN];
  point(){x=y=t=0;}
  point(int a,int b,int c){x=a;y=b;t=c;}
};
stack<point> s;
int main(){
  int i,j,si,sj,di,dj,temp;
  while(scanf("%d%d%d",&n,&m,&t)&&n||m||t){
    int w=0;
    for(i=0;i<n;i++){
      for(j=0;j<m;j++){
        scanf(" %c",&map[i][j]);
        if(map[i][j]=='X') w++;
        else if(map[i][j]=='S'){si=i;sj=j;}
        else if(map[i][j]=='D'){di=i;dj=j;}
      }
    }
    if(n*m-w<=t){printf("NO\n");continue;}
    success=false;
    while(!s.empty()) s.pop();
    point cur,tem;
    tem.x=si;tem.y=sj;tem.t=0;memcpy(tem.maze,map,81);tem.maze[si][sj]='X';
    s.push(tem);    
    int x,y,cnt;
    while(!s.empty()){
      cur=s.top();s.pop();
      x=cur.x;
      y=cur.y;
      cnt=cur.t;
      if(x==di&&y==dj&&cnt==t){
        success=true;
        break;
      }
      temp=(t-cnt)-abs(x-di)-abs(y-dj);
      if(temp<0||temp%2) continue;
      for(i=0;i<4;i++){
        int a=x+dir[i][0];
        int b=y+dir[i][1];
        if(a<0||a>=n||b<0||b>=m) continue;
        if(cur.maze[a][b]!='X'){
          tem.x=a;tem.y=b;tem.t=cnt+1;memcpy(tem.maze,cur.maze,81);
          tem.maze[a][b]='X';
          s.push(tem);
        }
      }
    }
    if(success) printf("YES\n");
    else printf("NO\n");
  }
}