1 一片1000*1000的草地，初始站在（1,1）(最左上角)，每一秒小易都会横向或纵向到相邻草地吃草(不会越界)，反派超超手上有n个陷阱，第i个陷阱位置（xi,yi），小易一旦进陷阱就会被捕获，为解救小易，请计算小易最少多少秒可能会走入一个陷阱，提前提醒小易
输入描述：第一行：n：超超的陷阱数
第二行：n个整数xi，表示陷阱横坐标
第三行：n个整数yi，表示陷阱纵坐标(坐标均在范围内)
#include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #include <queue> #include <limits.h> using namespace std; #define N 1005 struct PP { int x; int y; int step; }te, nt; int n; int a[N][N]; int dirx[] = { 1,0,-1,0 };//方向 int diry[] = { 0,1,0,-1 }; int vis[N][N]; int inx[N], iny[N]; int mi = INT_MAX; int check(int x, int y) //保证不越界、不二次进入 { if (x < 1 || x > 1000 || y < 1 || y > 1000 || vis[x][y] == 1) return 0; else return 1; } void bfs() { te.x = 1; te.y = 1; te.step = 0; vis[te.x][te.y] = 1; queue<PP> q; q.push(te); while (q.size() >= 1) { te = q.front(); q.pop(); if (a[te.x][te.y] == -1) { mi = te.step; return; } nt.step = te.step + 1; for (int i = 0; i < 4; i++) { nt.x = te.x + dirx[i]; nt.y = te.y + diry[i]; if (check(nt.x, nt.y) == 1) { vis[nt.x][nt.y] = 1; q.push(nt); } } } } int main() { //freopen("in.txt","r",stdin); while (scanf("%d", &n) != EOF) { int i; memset(a, 0, sizeof(a)); for (i = 0; i < n; i++) { scanf("%d", &inx[i]); } for (i = 0; i < n; i++) { scanf("%d", &iny[i]); a[inx[i]][iny[i]] = -1; } bfs(); printf("%d\n", mi); } }2 “回文串”正读反读均一样的字符串，“level”"noon"；花花有两个字符串A B，现他想将B插入A中使其变成回文串，求有多少种插入方法，B插入位置不一样就是不同方法
如：A="aba" B="b",有4种插入方法“baba” "abba" "abba" "abab" 答案为2
输入描述：
输入数据共两行；A、B；字符串<100，只包含小写字母
#include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #include <queue> #include <limits.h> using namespace std; #define N 1005 string s, t, c; int szs, szt; int ans; int check(string x) { int i = 0, j = x.size() - 1; while (i <= j) { if (x[i] != x[j]) return 0; i++; j--; } return 1; } void fun(int x) { c = s.substr(0, x) + t + s.substr(x); // << x << " " << c << endl; if (check(c) == 1) { ans++; } } int main() { //freopen("in.txt","r",stdin); //while(scanf("%d",&n) != EOF ) { while (cin >> s >> t) { szs = s.size(); szt = t.size(); ans = 0; int i; for (i = 0; i <= szs; i++) { fun(i); } printf("%d\n", ans); } }
3 二货小易有一个W*H的网格盒子，网格的行标号0~H-1，网格列标号0~W-1，每个格子至多放一块蛋糕，任意两块蛋糕的欧几里距离不能等于2.
(x1,y1),(x2,y2)的欧几里距离：(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)的算术平方根。
小易在网格内能够放多少块蛋糕？
输出描述：输出最多放的蛋糕数；
输入例子：3 2
输出：4
#include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #include <queue> #include <limits.h> using namespace std; #define N 1005 int a[N][N]; int n,m; int ans = 0; int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m) != EOF ) { //while(cin >> s >> t) { memset(a,0,sizeof(a)); int i,j,ni,nj; ans = 0; for(i = 0;i < n;i++){ for(j = 0;j < m;j++) { if(a[i][j] == -1) continue; ans++; ni = i + 2; nj = j; if(ni < n) { a[ni][nj] = -1; } ni = i; nj = j + 2; if(nj < m) { a[ni][nj] = -1; } } } printf("%d\n",ans); } }
