HDU查找（1）

HDU查找（1）

1010 Tempter of the Bone

dfs，在搜索前注意几点：
1.T必须大于等于最短距离，否则无解
2.T和最短距离的差必须是一个偶数，否则无解
3.在T没有减到0之前，不要走向终点
4.注意每次dfs后把刚踩的点变回’.’

#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<algorithm>using namespace std;
char c[8][8];
int n, m, t;
//起点与终点坐标
int sx, sy, dx, dy;
//起点到终点距离
int dis;bool exit(int t, int sx, int sy)
{//查看行走轨迹//printf("%d %d %dn", t, sx, sy);if (t == 0)return c[sy][sx] == 'D';//如果步数未走完已到终点if (c[sy][sx] == 'D')return false;bool flag = false;c[sy][sx] = 'X';//move upperif (!flag && sy != 0 && c[sy - 1][sx] != 'X'){flag |= exit(t - 1,  sx, sy - 1);}//move lowerif (!flag && sy != n - 1 && c[sy + 1][sx] != 'X'){flag |= exit(t - 1,  sx, sy + 1);}//move leftif (!flag && sx != 0 && c[sy][sx - 1] != 'X'){flag |= exit(t - 1, sx - 1, sy);}//move rightif (!flag && sx != m - 1 && c[sy][sx + 1] != 'X'){flag |= exit(t - 1,  sx + 1, sy);}c[sy][sx] = '.';return flag;
}int main()
{while (scanf("%d%d%d", &n, &m, &t) != EOF){if (!n && !m && !t)break;dis = 0;for (int i = 0; i < n; i++){scanf("%s", c[i]);for (int j = 0; j < m; j++){if (*(c[i] + j) == 'S'){sx = j;sy = i;}if (*(c[i] + j) == 'D'){dx = j;dy = i;}}}if (sx < dx)    {dis += dx - sx;}elsedis += sx - dx;if (sy < dy)    {dis += dy - sy;}elsedis += sy - dy;//多余步数是奇数则必定无法达到if ((t - dis) % 2){printf("NOn");continue;}if (exit(t,  sx, sy))printf("YESn");elseprintf("NOn");}
}

1016

1.先建立质数表
2.每次新加入一个元素时，依次尝试质数表中的每个质数减上一个元素（如果超出范围则放弃，如果已经存在则放弃）
3.每层dfs后要erase掉末尾元素
4.注意每行输出最后没有空格，否则PE

#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>using namespace std;vector<int> primeList;
vector<int> circle;
int num;void primeSearch(int n)
{primeList.push_back(3);for (int i = 5; i < n; i += 2){for (vector<int>::iterator it = primeList.begin(); *it <= sqrt(i); it++){if (i % *it == 0)goto C;}primeList.push_back(i);C:;}
}bool prime(int n)
{for (vector<int>::iterator it = primeList.begin(); it != d(); it++)if (*it == n)return true;return false;
}void dfs(int n, int lastval)
{if (!n && prime(*(d() - 1) + 1)){for (vector<int>::iterator it = circle.begin(); it != d() - 1; it++)printf("%d ", *it);printf("%dn", *(d() - 1));return;}for (vector<int>::iterator it = primeList.begin(); it != d(); it++){int thisval = *it - lastval;if (thisval < 1)continue;if (thisval > num){break;}for (vector<int>::iterator it2 = circle.begin(); it2 != d(); it2++){if (*it2 == thisval)goto C;}circle.push_back(thisval);dfs(n - 1, thisval);d() - 1);C:;}}int main()
{primeSearch(40);int i = 0;circle.push_back(1);while (scanf("%d", &num) != EOF){i++;if (num % 2){printf("Case %d:nn", i);continue;}printf("Case %d:n", i);dfs(num - 1, 1);printf("n");}}