首页 > 代码库 > NYOJ 搜索题目汇总 NYOJ 20、21、27、42、58、82、202、284、325、353、488、491、523、592、722

NYOJ 搜索题目汇总 NYOJ 20、21、27、42、58、82、202、284、325、353、488、491、523、592、722

NYOJ 搜索题目汇总





NYOJ 20

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int pre[100005];
vector<int>v[100005];//存储每个结点相邻的边

void DFS(int cur)
{
	for(int i = 0; i < v[cur].size(); ++i)//边
	{
		if(pre[v[cur][i]]) continue; //若存在父节点则继续遍历
		pre[v[cur][i]] = cur; //相连节点的父节点为cur
		DFS(v[cur][i]); //深搜到底,把一条路上父节点全部找出
	}
}

int main()
{
	int ncase, num, cur, i, x, y;
	scanf("%d", &ncase);
	while(ncase--)
	{
		memset(v, 0, sizeof(v));
		memset(pre, 0, sizeof(pre));
		scanf("%d %d", &num, &cur);
		pre[cur] = - 1; //起点没有父节点
		for(i = 0; i < num - 1; ++i)
		{
			scanf("%d %d", &x, &y);
			v[x].push_back(y); //x与y相连
			v[y].push_back(x); //y与x也肯定相连
		}
		DFS(cur); //起点开始深搜
		for(i = 1; i <= num; ++i)
			printf("%d ", pre[i]); //每个节点的父节点都保存在pri数组,输出即可
	}
	return 0;
}
        


NYOJ 21

法一:

 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

int total;
int v1, v2, v3;
bool visit[105][105][105]; //状态是否出现

struct state
{
	int a, b, c;
	int ceng; //最小步数
	state(){
		a = b = c = ceng = 0;
	}
}b, e;

int BFS(state begin)
{
	queue<state> q;
	while(!q.empty())
		q.pop();
	q.push(b);
	while(!q.empty())
	{
		state cur = q.front();
		q.pop();
		visit[cur.a][cur.b][cur.c] = true;

		if(cur.a == e.a && cur.b == e.b && cur.c == e.c) //找到
			return cur.ceng;

		if(cur.a > 0 && cur.b < v2)					//v1->v2
		{
			state temp = cur;
			int tt = min(temp.a, v2 - temp.b);
			temp.a -= tt;
			temp.b += tt;
			if(visit[temp.a][temp.b][temp.c] == false)
			{
				visit[temp.a][temp.b][temp.c] = true;
				temp.ceng++;
				q.push(temp);
			}
		}

		if(cur.a > 0 && cur.c < v3)					//v1->v3
		{
			state temp = cur;
			int tt = min(temp.a, v3 - temp.c);
			temp.a -= tt;
			temp.c += tt;
			if(visit[temp.a][temp.b][temp.c] == false)
			{
				visit[temp.a][temp.b][temp.c] = true;
				temp.ceng++;
				q.push(temp);
			}
		}

		if(cur.b > 0 && cur.a < v1)					//v2->v1
		{
			state temp = cur;
			int tt = min(temp.b, v1 - temp.a);
			temp.a += tt;
			temp.b -= tt;
			if(visit[temp.a][temp.b][temp.c] == false)
			{
				visit[temp.a][temp.b][temp.c] = true;
				temp.ceng++;
				q.push(temp);
			}
		}

		if(cur.b > 0 && cur.c < v3)					//v2->v3
		{
			state temp = cur;
			int tt = min(temp.b, v3 - temp.c);
			temp.b -= tt;
			temp.c += tt;
			if(visit[temp.a][temp.b][temp.c] == false)
			{
				visit[temp.a][temp.b][temp.c] = true;
				temp.ceng++;
				q.push(temp);
			}
		}

		if(cur.c > 0 && cur.a < v1)					//v3->v1
		{
			state temp = cur;
			int tt = min(temp.c, v1 - temp.a);
			temp.c -= tt;
			temp.a += tt;
			if(visit[temp.a][temp.b][temp.c] == false)
			{
				visit[temp.a][temp.b][temp.c] = true;
				temp.ceng++;
				q.push(temp);
			}
		}

		if(cur.c > 0 && cur.b < v2)					//v3->v2
		{
			state temp = cur;
			int tt = min(temp.c, v2 - temp.b);
			temp.c -= tt;
			temp.b += tt;
			if(visit[temp.a][temp.b][temp.c] == false)
			{
				visit[temp.a][temp.b][temp.c] = true;
				temp.ceng++;
				q.push(temp);
			}
		}
	}
	return -1; //没有终状态
}

int main()
{
	int ncase;
	scanf("%d", &ncase);
	while(ncase--)
	{
		total = 0;
		memset(visit, false, sizeof(visit));
		scanf("%d %d %d", &v1, &v2, &v3);
		b.a = v1, b.b = 0, b.c = 0, b.ceng = 0;
		scanf("%d %d %d", &e.a, &e.b, &e.c);
		if(v1 < e.a + e.b + e.c)
		{
			printf("-1\n");
			continue;
		}
		else
			printf("%d\n", BFS(b));
	}
	return 0;
}
        


法二:

 

#include <stdio.h>
#include <string.h>

#define MOVE(x) (x=(x+1)%1000)

bool state[100][100];
struct Size
{
	int e[3];
}queue[1000];

int V[3],E1,E2,E3;

int BFS()
{
	if(E1+E2+E3!=V[0])	return -1;
	else if(E1<0 || E2<0 || E3<0)	return -1;
	else if(V[0]==E1 && 0==E2 && 0==E3)	return 0;
	else	memset(state,false,sizeof(state));

	int tpe,cnt=0;
	int front,rear;
	int num,temp;
	Size s;

	front=rear=-1; s.e[0]=V[0]; s.e[1]=0; s.e[2]=0;
	queue[MOVE(rear)]=s; state[s.e[0]][s.e[1]]=true; num=1; temp=0;
   	while(front!=rear)
	{
		s=queue[MOVE(front)];
		if(--num==0)	cnt++;

		for(int i=0;i<3;i++)
		{
			if(s.e[i])
			{
				for(int j=(i+1)%3;j!=i;j=(j+1)%3)
				{
					tpe=(s.e[i]>V[j]-s.e[j])?(V[j]-s.e[j]):s.e[i];
					s.e[i]-=tpe;	s.e[j]+=tpe;
					if(s.e[0]==E1 && s.e[1]==E2 && s.e[2]==E3)	
						return num?cnt+1:cnt;

					if(!state[s.e[0]][s.e[1]])
					{
						queue[MOVE(rear)]=s;
						state[s.e[0]][s.e[1]]=true;
						temp++;
					}
					s.e[i]+=tpe;	s.e[j]-=tpe;
				}
			}
		}
		if(num==0)	num=temp,temp=0;
	}
	
	return -1;
}

int main()
{
	int t;
	
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d %d",&V[0],&V[1],&V[2]);
		scanf("%d %d %d",&E1,&E2,&E3);
		
		printf("%d\n",BFS());
	}
	return 0;
}        


NYOJ 27

 
#include<iostream>
#include<cstring>
const int N=100;
using namespace std;
int n,m;
int mp[N][N];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
void dfs(int si,int sj)
{
	mp[si][sj] = 0;
	int di,i,j;
	for(di=0;di<4;di++)
	{
		i = si + dir[di][0];
		j = sj + dir[di][1];
		if (i>=0 &&i<m && j>=0 && j<n && mp[i][j])
			dfs(i,j);
	}
}
int main()
{
	int t,cnt;
	cin>>t;
	while(t--)
	{
		cin>>m>>n;
		int i,j;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				cin>>mp[i][j];
		cnt = 0;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if (mp[i][j]==1)
				{
					cnt++;
					dfs(i,j);
				}
		cout<<cnt<<endl;
	}
	return 0;
}
        


NYOJ 42

#include<stdio.h>
#include<string.h>
int map[1050][1050],vis[1050],chu[1050];
int P,Q;
void dfs(int point)
{
    int i;
    vis[point]=1;//DFS 深度遍历
    for(i=1;i<=P;i++)
        if(map[point][i]!=0)
        {
           chu[point]++;
           if(vis[i]==0)
            dfs(i);
        }
}
int main()
{
    int i,j,N;
    scanf("%d",&N);
    while(N--)
    {
        int a,b;
        int all_vis=1;
        memset(map,0,sizeof(map));
        memset(vis,0,sizeof(vis));
        memset(chu,0,sizeof(chu));
        scanf("%d %d",&P,&Q);
        for(i=0;i<Q;i++)
        {
            scanf("%d %d",&a,&b);
            map[a][b]=1;
            map[b][a]=1;
        }
        dfs(1);
        for(i=1;i<P;i++)
        {
            if(vis[i]==0)
            {
                all_vis=0;
                break;
            }
        }
        if(all_vis==0) printf("No\n");
        else
        {
            j=0;
            for(i=1;i<=P;i++)
                if(chu[i]%2==1) j+=1;//欧拉图 度为奇数
            if(j==0||j==2) printf("Yes\n");
            else printf("No\n");
        }

    }
}

NYOJ 58

#include<stdio.h>
int a[9][9]={
1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,1,0,1,
1,0,0,1,1,0,0,0,1,
1,0,1,0,1,1,0,1,1,
1,0,0,0,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,0,0,0,1,
1,1,1,1,1,1,1,1,1};
int t,x1,x2,y1,y2,m;
int dfs(int x,int y,int s)
{
    if(x==x2&&y==y2){if(m>s)m=s;}
    else
        {
        if(!a[x+1][y])  {a[x+1][y]=1;dfs(x+1,y,s+1);a[x+1][y]=0;}
        if(!a[x-1][y])  {a[x-1][y]=1;dfs(x-1,y,s+1);a[x-1][y]=0;}
        if(!a[x][y+1])  {a[x][y+1]=1;dfs(x,y+1,s+1);a[x][y+1]=0;}
        if(!a[x][y-1])  {a[x][y-1]=1;dfs(x,y-1,s+1);a[x][y-1]=0;}
    }
}
int main()
{
    int s;
    scanf("%d",&t);
    while(t--)
    {
        m=81;s=0;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        dfs(x1,y1,s);
        printf("%d\n",m);
    }
return 0;
}


NYOJ 82

法一:

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef struct pos
{
   int x,y;
} POS;
int d[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int bfs(POS from);

char maze[20][20];
int key[5];
queue<pos> que;
int row,col;
POS start;

int main()
{
   int i,j;

     while(scanf("%d%d",&row,&col) && (row + col))
     {
         for(i = 0 ; i < 5 ; ++i)
         key[i] = 0;

         for(i = 0 ; i < row ; ++i)
         {
               scanf("%s",maze[i]);
               for(j = 0 ; j < col ; ++j)
               {
                 if(maze[i][j] == 'S')//记录起点
                 {
                      start.x = i; start.y = j;
                 }
                 if(maze[i][j]>= 'a' && maze[i][j]<= 'e')//统计各个门所需的钥匙数量
                    ++key[maze[i][j]-'a'];
               }
         }//for(i)

         que.push(start);

         if(bfs(start)) puts("YES");
         else    puts("NO");

         while(!que.empty())  que.pop();

     }

    // system("pause");
     return 0;
}

int bfs(POS from)
{
    POS p,next;
    int i,t;
    maze[from.x][from.y] = 'X';

     while(!que.empty())
     {
         p = que.front();
         que.pop();

         for(i = 0 ; i < 4 ; ++i)
         {
            next.x = p.x + d[i][0];
            next.y = p.y + d[i][1];
            if(next.x>=0 && next.x < row && next.y>=0 && next.y < col)
            {
                  if(maze[next.x][next.y] == 'G')//找到终点,结束
                   return true;

                  if(maze[next.x][next.y] == '.')//可以走 进队列
                  {
                    que.push(next);
                    maze[next.x][next.y] = 'X';
                  }
                  else
                  {
                      if(maze[next.x][next.y]>='a' && maze[next.x][next.y] <= 'e')
                      {
                        que.push(next);
                        --key[maze[next.x][next.y]-'a'];//记录找到的钥匙数量
                        maze[next.x][next.y] = '.';
                      }
                      else
                      if(maze[next.x][next.y]>='A' && maze[next.x][next.y] <= 'E')
                      {
                        t = maze[next.x][next.y] - 'A';

                        /*
                            这个地方相当关键啊!
                        */
                        if(!key[t])//用钥匙把门打开即可
                        {
                          que.push(next);
                         // maze[next.x][next.y] = 'X';
                        }
                        else//钥匙不够,就把原来的p进队列,先走其他的路,以寻找其他的钥匙
                        {
                              if(!que.empty())  que.push(p);
                        }
                      }
                }
           }//if
         }//for()
    }//while()
    return 0;
}


法二:

#include <queue>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
using namespace std;
typedef struct
{
    int x,y;
}Ac;
queue <Ac> S,door[5];
int dir[]={0,1,0,-1,1,0,-1,0};
int from_x,from_y,to_x,to_y;
int lock[5],key[5];
int map[25][25];
bool in[25][25];
bool bfs()
{
    while(!S.empty())
    {
        Ac R = S.front();
        S.pop();
        if(R.x == to_x && R.y == to_y)
            return true;
        for(int k=0;k<8;)
        {
            int x = R.x + dir[k++];
            int y = R.y + dir[k++];
            if(!in[x][y] && map[x][y])    //路或钥匙
            {
                S.push({x,y});
                in[x][y]=1;
                if(map[x][y]>0)           //钥匙
                {
                    key[map[x][y]-1]++;
                    map[x][y]=-1;
                }

            }
        }
        if(S.empty())
        {
            memset(in,0,sizeof(in));
            int find=0;
            for(int i=0;i<5;i++)
            {
                if(key[i] && key[i]==lock[i])//芝麻开门
                {
                    key[i]=0,find=1;
                    while(!door[i].empty())
                    {
                        R = door[i].front();
                        int x = R.x;
                        int y = R.y;
                        map[x][y]=-1;
                        door[i].pop();
                    }
                }
            }
            if(find)
                S.push({from_x,from_y});
            else
                break;
        }
    }
    return false;
}
void clear()
{
    while(!S.empty())
        S.pop();
    for(int i=0;i<5;i++)
        while(!door[i].empty())
            door[i].pop();
}
int main()
{
    int h,w;
    while(scanf("%d%d",&h,&w),h||w)
    {
        getchar();
        memset(lock,0,sizeof(lock));
        memset(map,0,sizeof(map));
        memset(key,0,sizeof(key));
        memset(in,0,sizeof(in));
        for(int i=1;i<=h;i++)
        {
            for(int j=1;j<=w;j++)
            {
                char c = getchar();
                switch(c)
                {
                    case 'S':from_x=i;from_y=j;S.push({i,j});break;
                    case 'G':to_x=i,to_y=j;
                    case '.':map[i][j]=-1;break;
                }
                if(islower(c))                             //钥匙
                {
                    lock[c-'a']++;
                    map[i][j] = c-'a'+1;
                }
                if(isupper(c) && c!='G' && c!='S' && c!='X')//门
                {
                    door[c-'A'].push({i,j});
                }
            }
            getchar();
        }
        bool yes=bfs();
        if(yes)
            puts("YES");
        else
            puts("NO");
        clear();
    }
    return 0;
}


NYOJ 202

 
#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;

const int N = 15;
int x[N],y[N],z[N],leftp[N],rightp[N];

void midorder(int x)
{
    if(x != -1)
	{
	   midorder(leftp[x]);
	   printf("%d\n",x);
	   midorder(rightp[x]);
	}
}

int main()
{
    int numcase;
    scanf("%d",&numcase);
    for(int k = 1;k <= numcase;++k)
    {
        int n;
        scanf("%d",&n);
        for(int i = 0;i < n;++i)
        {
           scanf("%d%d%d",&x[i],&y[i],&z[i]);
        }
        for(int i = 0;i < n;++i)
        {
            leftp[x[i]] = y[i];
            rightp[x[i]] = z[i];
        }
        int m,xx,yy;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&xx,&yy);
        }
		midorder(0);
		printf("\n");
    }
    return 0;
}
        


NYOJ 284

法一:

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef struct node
{
    int x,y,step;
}node;
bool operator<(const node &a,const node &b)
{
    return a.step>b.step;
}
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int main()
{
    char map[305][305];
    int i,j,ans,n,m;
    node a,b;
    priority_queue<node>q;
    while(scanf("%d %d",&n,&m)&&(n||m))
    {
        a.x=0;
        for(i=0;i<n;i++)
        {
            scanf("%s*c",&map[i]);
            for(j=0;j<m;j++)
            {
                if(map[i][j]=='Y')
                {
                    a.x=i;
                    a.y=j;
                    a.step=0;
                    q.push(a);
                }
            }
        }
        bool flag=false;
        while(!q.empty())//广搜
        {
            a=q.top();
            q.pop();
            for(i=0;i<4;i++)
            {
                b.x=a.x+dir[i][0];
                b.y=a.y+dir[i][1];
                if(b.x>=0 && b.x<n && b.y>=0 && b.y<m)
                {
                    if(map[b.x][b.y]=='T')
                    {
                        ans=a.step+1;
                        flag=true;
                        break;
                    }
                    else if(map[b.x][b.y]=='E')
                    {
                        b.step=a.step+1;
                        q.push(b);
                        map[b.x][b.y]='S';
                    }
                    else if(map[b.x][b.y]=='B')
                    {
                        b.step=a.step+2;
                        q.push(b);
                        map[b.x][b.y]='S';
                    }
                }
            }
            if(flag)
                break;
        }
        if(flag)
            printf("%d\n",ans);
        else
            printf("-1\n");
        while(!q.empty())
        {
            q.pop();
        }
    }
    return 0;
}

法二:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int m, n;
struct node{
    int x, y;
    node(int a, int b){
        x = a; y = b;
    }
}*xm, *d;
char maze[301][301];
int dist[301][301], steps;
bool vis[301][301];
queue<node*> q;
void PUSH(int a, int b){
    if(vis[a][b] || a < 1 || b < 1 || a > m || b > n || maze[a][b] == 'S' || maze[a][b] == 'R') return;
    q.push(new node(a, b));
    dist[a][b] = steps+1;
    vis[a][b] = 1;
}
int bfs(){
    memset(vis, 0, sizeof(vis));
    memset(dist, 0, sizeof(dist));
    node *cur = new node(xm->x, xm->y);
    while(!q.empty()) q.pop();
    q.push(cur);
    vis[xm->x][xm->y] = 1;
    while(!q.empty()){
        cur = q.front(); q.pop();
        steps = dist[cur->x][cur->y];
        if(cur->x == d->x && cur->y == d->y)
            return dist[d->x][d->y];

        if(maze[cur->x][cur->y] == 'B'){
            maze[cur->x][cur->y] = 'E';
            vis[cur->x][cur->y] = 0;
            PUSH(cur->x, cur->y);
        }else if(maze[cur->x][cur->y] != 'R' || maze[cur->x][cur->y] != 'S'){
            PUSH(cur->x - 1, cur->y);
            PUSH(cur->x, cur->y - 1);
            PUSH(cur->x, cur->y + 1);
            PUSH(cur->x + 1, cur->y);
        }
    }
    return -1;
}
int main(){
    int i, j;
    while(scanf("%d%d", &m, &n) && m||n){
        for(i = 1; i <= m; i++)
            for(j = 1; j <= n; j++){
                scanf(" %c ", &maze[i][j]);
                if(maze[i][j] == 'Y')
                    xm = new node(i, j);
                else if(maze[i][j] == 'T')
                    d = new node(i, j);
            }
        printf("%d\n", bfs());
    }
    return 0;
}

priority_queue

#include<iostream>
#include<functional>
#include<queue>
#include<vector>
using namespace std;

//定义比较结构
struct cmp1{
    bool operator ()(int &a,int &b){
        return a>b;//最小值优先
    }
};

struct cmp2{
    bool operator ()(int &a,int &b){
        return a<b;//最大值优先
    }
};

//自定义数据结构
struct number1{
    int x;
    bool operator < (const number1 &a) const {
        return x>a.x;//最小值优先
    }
};
struct number2{
    int x;
    bool operator < (const number2 &a) const {
        return x<a.x;//最大值优先
    }
};
int a[]={14,10,56,7,83,22,36,91,3,47,72,0};
number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0};
number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0};

int main()
{
    priority_queue<int>que;//采用默认优先级构造队列

    priority_queue<int,vector<int>,cmp1>que1;//最小值优先
    priority_queue<int,vector<int>,cmp2>que2;//最大值优先

    priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误,
    priority_queue<int,vector<int>,less<int> >que4;////最大值优先

    priority_queue<number1>que5; //最小优先级队列
    priority_queue<number2>que6;  //最大优先级队列

    int i;
    for(i=0;a[i];i++){
        que.push(a[i]);
        que1.push(a[i]);
        que2.push(a[i]);
        que3.push(a[i]);
        que4.push(a[i]);
    }
    for(i=0;num1[i].x;i++)
        que5.push(num1[i]);
    for(i=0;num2[i].x;i++)
        que6.push(num2[i]);


    printf("采用默认优先关系:/n(priority_queue<int>que;)/n");
    printf("Queue 0:/n");
    while(!que.empty()){
        printf("%3d",que.top());
        que.pop();
    }
    puts("");
    puts("");

    printf("采用结构体自定义优先级方式一:/n(priority_queue<int,vector<int>,cmp>que;)/n");
    printf("Queue 1:/n");
    while(!que1.empty()){
        printf("%3d",que1.top());
        que1.pop();
    }
    puts("");
    printf("Queue 2:/n");
    while(!que2.empty()){
        printf("%3d",que2.top());
        que2.pop();
    }
    puts("");
    puts("");
    printf("采用头文件/"functional/"内定义优先级:/n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)/n");
    printf("Queue 3:/n");
    while(!que3.empty()){
        printf("%3d",que3.top());
        que3.pop();
    }
    puts("");
    printf("Queue 4:/n");
    while(!que4.empty()){
        printf("%3d",que4.top());
        que4.pop();
    }
    puts("");
    puts("");
    printf("采用结构体自定义优先级方式二:/n(priority_queue<number>que)/n");
    printf("Queue 5:/n");
    while(!que5.empty()){
        printf("%3d",que5.top());
        que5.pop();
    }
    puts("");
    printf("Queue 6:/n");
    while(!que6.empty()){
        printf("%3d",que6.top());
        que6.pop();
    }
    puts("");
    return 0;
}
/*
运行结果 :
采用默认优先关系:
(priority_queue<int>que;)
Queue 0:
83 72 56 47 36 22 14 10  7  3

采用结构体自定义优先级方式一:
(priority_queue<int,vector<int>,cmp>que;)
Queue 1:
 7 10 14 22 36 47 56 72 83 91
Queue 2:
83 72 56 47 36 22 14 10  7  3

采用头文件"functional"内定义优先级:
(priority_queue<int,vector<int>,greater<int>/less<int> >que;)
Queue 3:
 7 10 14 22 36 47 56 72 83 91
Queue 4:
83 72 56 47 36 22 14 10  7  3

采用结构体自定义优先级方式二:
(priority_queue<number>que)
Queue 5:
 7 10 14 22 36 47 56 72 83 91
Queue 6:
83 72 56 47 36 22 14 10  7  3
*/

法三:

#include <iostream>
 #include <queue>
 #include <cstdio>
 #include <cstring>
 using namespace std;
 #define  max 301
 char map[max][max];
 int n,m;
 bool vist[max][max];
 int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

 struct node
 {
     int x,y,c;
     friend bool operator <(const node &s1,const node &s2)
     {
         return s1.c>s2.c;
     }
 };
 node s,e;

 int bfs()
 {
     priority_queue < node > q;
     memset(vist,0,sizeof(vist));
     node now,t;
     s.c=0;
     q.push(s);
     vist[s.x][s.y]=1;
     while (!q.empty())
     {
         now=q.top();
         q.pop();
         if (now.x==e.x&&now.y==e.y)
         {
             return now.c;
         }
         for (int i=0;i<4;i++)
         {
             t.x=now.x+d[i][0];
             t.y=now.y+d[i][1];
             if (t.x>=0&&t.x<n&&t.y>=0&&t.y<m&&!vist[t.x][t.y])
             {
                 vist[t.x][t.y]=1;
                 if (map[t.x][t.y]=='B')
                 {
                     t.c=now.c+2;
                     q.push(t);
                 }
                 else
                     if (map[t.x][t.y]=='E'||map[t.x][t.y]=='T')
                     {
                         t.c=now.c+1;
                         q.push(t);
                     }
             }
         }
     }
     return -1;
 }

 int main()
 {
     int i,j;
     while (cin>>n>>m,m+n)
     {
         for (i=0;i<n;i++)
         {
             for (j=0;j<m;j++)
             {
                 cin>>map[i][j];
                 if (map[i][j]=='Y')
                     s.x=i,s.y=j;
                 if (map[i][j]=='T')
                     e.x=i,e.y=j;
             }
         }
         int sum=bfs();
      cout<<sum<<endl;
     }

     return 0;
 }


NYOJ 325

 
#include <stdio.h>
#define max(a,b) a>b?a:b
int V,ans,n,w[21],sum[21];
void dfs(int i,int cnt)
{
    if(i == 0)
    {
        ans = max(ans,cnt);
        return ;
    }
    if(ans == V || cnt+sum[i] <= ans)       //cut
        return ;
    if(cnt+w[i] <= V)
        dfs(i-1,cnt+w[i]);
    dfs(i-1,cnt);
}
int main()
{
    while(~scanf("%d",&n))
    {
        ans = 0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
            sum[i] = sum[i-1] + w[i];
        }
        V = sum[n]/2;
        dfs(n,0);
        printf("%d\n",sum[n]-2*ans);
    }
    return 0;
}        


NYOJ 353

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 35;
const int INF = 0xfffffff;

struct Node
{
    int x, y, z;
    int step;
    Node()
    {
        x = y = z = 0;
        step = 0;
    }
};

Node TargetPos;
char Graph[MAXN][MAXN][MAXN];
int MinTime[MAXN][MAXN][MAXN];
int row, col, level;

int dir[6][3] = {{1, 0, 0}, {0, 1, 0}, {-1, 0, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};


bool Is_CanGo(Node CurPos)
{
    if(CurPos.x < 0 || CurPos.x >= level || CurPos.y < 0 || CurPos.y >= row || CurPos.z < 0 || CurPos.z >= col || Graph[CurPos.x][CurPos.y][CurPos.z] == '#')
        return false;
    return true;
}

void BFS(Node S)
{
    queue <Node> Que;
    Que.push(S);
    while(!Que.empty())
    {
        Node Curpos = Que.front();
        Que.pop();

        for(int i = 0; i < 6; ++i)
        {
            Node t;
            t.x = Curpos.x + dir[i][0];
            t.y = Curpos.y + dir[i][1];
            t.z = Curpos.z + dir[i][2];

            if(Is_CanGo(t))
            {
                t.step = Curpos.step + 1;
                if(t.step < MinTime[t.x][t.y][t.z])
                {
                    MinTime[t.x][t.y][t.z] = t.step;
                    Que.push(t);
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d %d %d", &level, &row, &col) && (level + row + col))
    {
        Node StartPos;
        for(int i = 0; i < level; ++i)
        {
            for(int j = 0; j < row; ++j)
            {
                scanf("%s", Graph[i][j]);
                for(int z = 0; z < col; ++z)
                {
                    MinTime[i][j][z] = INF;
                    if(Graph[i][j][z] == 'S')
                        StartPos.x = i, StartPos.y = j, StartPos.z = z;
                    else if(Graph[i][j][z] == 'E')
                        TargetPos.x = i, TargetPos.y = j, TargetPos.z = z;
                }
                getchar();
            }
           if(i != level - 1)
                getchar();
        }
        StartPos.step = 0;
        BFS( StartPos );
        int t;
        t = MinTime[TargetPos.x][TargetPos.y][TargetPos.z];
        if(t != INF)
            printf("Escaped in %d minute(s).\n", t);
        else
            printf("Trapped!\n");
    }
    return 0;
}


NYOJ 488

#include<stdio.h>
#include<string.h>
int Map[9][9],floag;
int IsCan(int number,int x,int y){//判断Numebr是否满足数独的条件
    int i,j;
    for(i=0;i<9;i++){
        if(Map[i][y]==number){
            return 0;
        }
    }
    for(i=0;i<9;i++){
        if(Map[x][i]==number){
            return 0;
        }
    }
    x=x/3*3,y=y/3*3;
    for(i=x;i<x+3;i++)
        for(j=y;j<y+3;j++)
            if(Map[i][j]==number)
            return 0;

    return 1;
}
void dfs(int x,int y){
    if(floag) return ;//floag用于标记,当所有数据都搜完的时候就给跳出
    if(x==9 && y==0){
        int i,j;
        for(i=0;i<9;i++){
            for(j=0;j<9;j++){
                printf("%d ",Map[i][j]);
            }
                printf("\n");
        }
            floag=1;
        return ;
    }
    if(y==9){//一行结束进入下一行
        dfs(x+1,0);
    }
    if(Map[x][y]!=0){//已经有数就填下一个
        dfs(x,y+1);
    }
    if(Map[x][y]==0){
        int i;
        for(i=1;i<=9;i++){
            if(IsCan(i,x,y)){
                Map[x][y]=i;
                dfs(x,y+1);
                Map[x][y]=0;//回溯清除,当一次搜索结束的时候但是不满足就将之前的结果清除
            }
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int i,j;
        for(i=0;i<9;i++){
            for(j=0;j<9;j++){
                scanf("%d",&Map[i][j]);
            }
        }
        dfs(0,0);
        memset(Map,0,sizeof(Map));
        floag=0;
    }
    return 0;
}


NYOJ 491

法一:

#include"iostream"
#include<cstring>
#include<stdio.h>
#include<time.h>
using namespace std;
typedef unsigned char uchar;

//char cc[2]={'+','-'};    //便于输出
int n,                     //第一行符号总数
    half,                 //全部符号总数一半
    counter;             //1计数,即  '-' 号计数

char **p;                //符号存储空间
long sum;                //符合条件的三角形计数

//t,第一行第 t个符号
void Backtrace(int t)
{
    int i, j;

    if( t > n )
        sum++;
    else
    {
       for(i=0; i<2; ++i)  //只取  0('+')  或者  1('-')
       {
            p[1][t] = i;   //第一行第 t个符号
            counter += i;        //'-'号统计
            for(j=2; j<=t; ++j)    //当第一行符号 >=2时,可以运算出下面行的某些符号(第一行有几个数就可以相应往下计算几行,每次计算过的就不用重复计算)
            {
                p[j][t-j+1] = p[j-1][t-j+1]^p[j-1][t-j+2];//通过异或运算下行符号
                counter += p[j][t-j+1];
            }
            if( (counter <= half) && ( t*(t+1)/2 - counter <= half) )//若符号统计未超过半数,并且另一种符号也未超过半数
                Backtrace(t+1);            //在第一行增加下一个符号
            //回溯,判断另一种符号情况
            for(j=2; j<=t; ++j)
                counter -= p[j][t-j+1];
            counter -= i;
       }
    }
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        counter = 0;
        sum = 0;
        half = n*(n+1)/2;

        if( half%2 == 0 )//总数须为偶数,若为奇数则无解
        {
            half /= 2;
            p = new char *[n+1];
            for(int i=0; i<=n; ++i)
            {
               p[i] = new char[n+1];
               memset(p[i], 0, sizeof(char)*(n+1));
            }
            Backtrace(1);
        }
        printf("%d\n", sum);
    }
    return 0;
}

法二:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;

#define M 20
int cnt,zcnt,fcnt,res[M];
bool ope[M][M];
void dfs1(int n,int p)
{
	if(p == n)
	{
		zcnt = fcnt = 0;
		for(int i = 1;i <= p;++i)//
			for(int j = 1;j <= p - i + 1;++j)
			{
				if(ope[i-1][j]) fcnt++;
				else zcnt++;
				if(j == p - i + 1) continue;
				if(ope[i-1][j] == ope[i-1][j+1]) ope[i][j] = false;
				else ope[i][j] = true;
			}
			if(zcnt == fcnt && zcnt) cnt++;
			return ;
	}
	dfs1(n,p+1);
	ope[0][p+1] = true;
	dfs1(n,p+1);
	ope[0][p+1] = false;
}
void init()
{
	for(int i = 1;i < 20;++i)
	{
		memset(ope,0,sizeof(ope));
		cnt = 0;
		if((i*(i+1)/2)%2==0) dfs1(i,0);
		res[i] = cnt;
	}
}
int main()
{
	int n;init();
	while(~scanf("%d",&n))
	{
		printf("%d\n",res[n]);
	}
	return 0;
}
/*
枚举第一行所有的情况,可以用深搜实现,可根据第一行逐行确定出下一行的状态,,然后算出每种情况两种符号的个数,在运算之前可以先进行一下判断,当(n+1)*n/2为奇数时,结果为零
*/
//超时

NYOJ 499

法一:

#include<stdio.h>
#include<string.h>

int a[10][10], count, n, m;
int b[10][10];
void DFS(int x, int y)
{
	if(x > n || x < 1 || y > m || y < 1 || a[x][y] == 1)
	{

		return ;
	}
	if(x == n && y == m)
	{
		count++;
		return ;
	}
	printf("%d,%d\n",x,y);
	a[x][y] = 1;
	DFS(x + 1, y);
	DFS(x - 1, y);
	DFS(x, y + 1);
	DFS(x, y - 1);
	a[x][y] = 0;
}


int main()
{
	int t, i, j;
	scanf("%d", &t);
	while(t--)
	{
		count = 0;
		memset(b, 0, sizeof(b));
		scanf("%d%d", &n, &m);
		for(i = 1; i <= n; i++)
		{
			for(j = 1; j <= m; j++)
			{
				scanf("%d", &a[i][j]);
			}
		}
		DFS(1, 1);
		printf("%d\n", count);
	}
	return 0;
}
/*0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1*/


法二:

#include <stdio.h>

int count;
int dt[8][8];
int r,c;

void init()
{
	int i;
	for(i = 0 ; i <= r+1; i++)
	{
		dt[i][0] = 1;
		dt[i][c+1] = 1;
	}
	for(i = 0; i <= c+1; i++)
	{
		dt[0][i] = 1;
		dt[r+1][i] = 1;
	}
}
void print()
{
	int i,j;
	for(i = 0; i <= r+1; i++)
	{
		for(j = 0; j <= c+1; j++)
			printf("%d ",dt[i][j]);
		printf("\n");
	}
}
void dfs(int x,int y)
{
	if(x == r && y == c)
	{
		count++;
		return;
	}
	dt[x][y] = 1;
	if(!dt[x+1][y]) dfs(x+1,y);
	if(!dt[x][y+1]) dfs(x,y+1);
	if(!dt[x-1][y]) dfs(x-1,y);
	if(!dt[x][y-1]) dfs(x,y-1);
	dt[x][y] = 0;

}

int main()
{
	int i,j,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&r,&c);
		count = 0;
		init();
		for(i = 0; i < r; i++)
			for(j = 0; j < c; j++)
				scanf("%d", &dt[i+1][j+1]);
		dfs(1,1);
		printf("%d\n",count);
	}
	return 0;
}


NYOJ 523

法一:

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

int map[55][55][55],f[]={1,-1,0,0,0,0},g[]={0,0,1,-1,0,0},w[]={0,0,0,0,1,-1};
bool vis[55][55][55],flag;
struct Node
{
    int x,y,z,step;
};

int bfs(int a,int b,int c,int time)
{
    int i,j,k;
     int r,s,t;
    memset(vis,0,sizeof(vis));
    queue <Node> q;
    Node temp={0,0,0,time};
    vis[0][0][0]=1;
    q.push(temp);
    while(!q.empty())
    {
        temp=q.front();
        q.pop();
        for(i=0;i<6;i++)
        {
            r=temp.x+f[i];
            s=temp.y+g[i];
            t=temp.z+w[i];
            if(r>=0&&r<a&&s>=0&&s<b&&t>=0&&t<c&&vis[r][s][t]==0)
            {
                if(r==a-1&&s==b-1&&t==c-1&&map[r][s][t]==0&&temp.step-1>=0)
                {
                    flag=1;
                    break;
                }
                else if(map[r][s][t]==0&&temp.step-1)
                {
                    Node next={r,s,t,temp.step-1};
                    q.push(next);
                    vis[r][s][t]=1;
                }
            }
        }
        if(flag==1||temp.step-1==0)
            break;
    }
    while(!q.empty())
        q.pop();
    return time-(temp.step-1);
}

int main()
{
    int a,b,c;
     int i,j,k,T;
     int time;
    scanf("%d",&T);
    while(T--)
    {
        memset(map,0,sizeof(map));
        flag=0;
        scanf("%d%d%d%d",&a,&b,&c,&time);
        for(k=0;k<a;k++)
        {
            for(i=0;i<b;i++)
            {
                for(j=0;j<c;j++)
                {
                    scanf("%d",&map[k][i][j]);
                }
            }
        }
        int cnt=bfs(a,b,c,time);
        if(flag==1)
            printf("%d\n",cnt);
        else
            printf("-1\n");
    }
    return 0;
}

法二:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

const int N = 55;
const int dir[6][3] = {{0, 0, 1}, {0, 0, -1}, {-1, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, -1, 0}};

struct node
{
	int x, y, z;
	int ceng;
}que[50000];

int maze[N][N][N];
int a, b, c, t;
int num;
int head, tail;

int Scan()
{
	int res = 0 , ch;
	while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) )
	{
		if( ch == EOF )  return 1 << 30 ;
	}
	res = ch - '0' ;
	while( ( ch = getchar() ) >= '0' && ch <= '9' )
		res = res * 10 + ( ch - '0' ) ;
	return res ;
}

int BFS()
{
	node cur;
	cur.x = 1, cur.y = 1, cur.z = 1, cur.ceng = 0;
	maze[cur.x][cur.y][cur.z] = 0;

	que[tail++] = cur;
	while(head < tail)
	{
		node temp = que[head++];

		if(temp.ceng > t) //无法到达
			return -1;
		if(temp.x == a && temp.y == b && temp.z == c && temp.ceng <= t)
			return temp.ceng;

		for(int i = 0; i < 6; ++i)
		{
			node now;
			now.x = temp.x + dir[i][0]; now.y = temp.y + dir[i][1]; now.z = temp.z + dir[i][2];
			if(maze[now.x][now.y][now.z])
			{
				now.ceng = temp.ceng + 1;
				que[tail++] = now;
				maze[now.x][now.y][now.z] = 0;
			}
		}
	}
	return -1;
}

int main()
{
	int ncase;
	ncase = Scan();
	while(ncase--)
	{
		num = head = tail = 0;
		memset(maze, 0, sizeof(maze));
		a = Scan(), b = Scan(), c = Scan(), t = Scan();
		for(int i = 1; i <= a; ++i)
			for(int j = 1; j <= b; ++j)
				for(int k = 1; k <= c; ++k)
				{
					maze[i][j][k] = Scan() ^ 1;
					num += maze[i][j][k];
				}

		if(maze[a][b][c] == 0 || num < a + b + c - 3) //终点无法走
		{
			printf("-1\n");
			continue;
		}
		printf("%d\n", BFS());
	}
	return 0;
}



NYOJ 592

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int map[105][105]={0};
int mm=10000,n=100;
int fir,end,loop[105][105];
int prime[11000]={1,1,0};
int sx[]={0,0,1,-1},zy[]={1,-1,0,0};
void Build_map() //建立地图
{
    int i,j,k;
    for(i=1;i<=(n+1)/2;i++)
    {
        for(j=1;j<=n-2*i+2;j++)
            map[i][j+i-1]=mm--;
        for(j=1;j<=n-2*i;j++)
           map[j+i][n-i+1]=mm--;
        for(j=n-i+1;j>=i;j--)
           map[n-i+1][j]=mm--;
        for(j=n-i;j>=i+1;j--)
           map[j][i]=mm--;
    }
}
void printf_map()//打印地图
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
          printf("%d ",map[i][j]);
        printf("\n");
    }

}
void judge_prime()  //筛选法打个素数表
{
    int i,j;
    for(i=2;i<=10000;i++)
    {
        if(prime[i]==0)
        {
            for(j=i+i;j<=10000;j+=i)
              prime[j]=1;
        }
    }
}
struct coordinate
{
    int x;
    int y;
    int step;
}t1;
void find() //找到 fir 的坐标,存在 t1 中
{
    int i,j;
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
      {
          if(map[i][j]==fir)
          {
              t1.x=i;
              t1.y=j;
              loop[i][j]=1;
              t1.step=0;
              return;
          }
      }
}
int bfs()
{
    int i,j,step,x,y;
    queue<coordinate> Q;
    Q.push(t1);
    while(!Q.empty())
    {
        i=Q.front().x;
        j=Q.front().y;
        step=Q.front().step;
        Q.pop();
        if(map[i][j]==end)
          return step;
        for(int a=0;a<4;a++)
        {
            x=i+sx[a];
            y=j+zy[a];
            if(map[x][y]!=0&&prime[map[x][y]]==1&&loop[x][y]==0)
            {
                coordinate t2={x,y,step+1};
                Q.push(t2);
                loop[x][y]=1;
            }
        }
    }
    return 0;
}
int main()
{
    int i,j,nn=0;
    Build_map();
    judge_prime();
    //printf_map();
    while(~scanf("%d%d",&fir,&end))
    {
        nn++;
        memset(loop,0,sizeof(loop));
        find();
        int ans=bfs();
        if(ans)
            printf("Case %d: %d\n",nn,ans);
        else
            printf("Case %d: impossible\n",nn);
    }
}


NYOJ 722

#include<stdio.h>
#include<string.h>
int Map[9][9],floag;
int IsCan(int number,int x,int y){//判断Numebr是否满足数独的条件
    int i,j;
    for(i=0;i<9;i++){
        if(Map[i][y]==number){
            return 0;
        }
    }
    for(i=0;i<9;i++){
        if(Map[x][i]==number){
            return 0;
        }
    }
    x=x/3*3,y=y/3*3;
    for(i=x;i<x+3;i++)
        for(j=y;j<y+3;j++)
            if(Map[i][j]==number)
            return 0;

    return 1;
}
void dfs(int x,int y){
    if(floag) return ;//floag用于标记,当所有数据都搜完的时候就给跳出
    if(x==9 && y==0){
        int i,j;
        for(i=0;i<9;i++){
            for(j=0;j<9;j++){
                printf("%d ",Map[i][j]);
            }
                printf("\n");
        }
            floag=1;
        return ;
    }
    if(y==9){//一行结束进入下一行
        dfs(x+1,0);
    }
    if(Map[x][y]!=0){//已经有数就填下一个
        dfs(x,y+1);
    }
    if(Map[x][y]==0){
        int i;
        for(i=1;i<=9;i++){
            if(IsCan(i,x,y)){
                Map[x][y]=i;
                dfs(x,y+1);
                Map[x][y]=0;//回溯清除,当一次搜索结束的时候但是不满足就将之前的结果清除
            }
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int i,j;
        for(i=0;i<9;i++){
            for(j=0;j<9;j++){
                scanf("%d",&Map[i][j]);
            }
        }
        dfs(0,0);
        memset(Map,0,sizeof(Map));
        floag=0;
    }
    return 0;
}



NYOJ 搜索题目汇总 NYOJ 20、21、27、42、58、82、202、284、325、353、488、491、523、592、722