算法 - Ruilin

纪念一下刷的第100道水题

11月 4, 2017
0 条评论

纪念一下本辣鸡在hdu刷的第100道水题，
比较标准的dfs..

Red and Black

Problem Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

‘.’ – a black tile
‘#’ – a red tile
‘@’ – a man on a black tile(appears exactly once in a data set)

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9
….#.
…..#
……
……
……
……
……
#@…#
.#..#.
11 9
.#………
.#.#######.
.#.#…..#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#…….#.
.#########.
………..
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
…@…
###.###
..#.#..
..#.#..
0 0

Sample Output

45
59
6
13

代码实现

import java.util.Scanner;

public class Dfs1312 {
	public static char a[][];
	public static int book[][];
	public static int l;
	public static int h;
	public static int sum;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			l = in.nextInt();
			h = in.nextInt();
			if (h == 0 && l == 0) {
				break;
			}
			a = new char[h][l];
			int startx = 0;
			int starty = 0;
			book = new int[h][l];// 没走的记录为0
			for (int i = 0; i < h; i++) {
				String str = in.next();
				in.nextLine();
				a[i] = str.toCharArray();
				for (int j = 0; j < l; j++) {
					if (a[i][j] == '@') {// 记录出发点
						startx = i;
						starty = j;
					}
				}
			}
			book[startx][starty] = 1;// 标记出发点已走
			sum = 1;
			dfs(startx, starty);
			System.out.println(sum);
		}
	}

	static void dfs(int x, int y) {
		int[][] next = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
		int tx, ty;
		for (int i = 0; i < 4; i++) {// 计算下一点坐标
			tx = x + next[i][0];
			ty = y + next[i][1];
			// 判断是否越界
			if (tx < 0 || tx >= h || ty < 0 || ty >= l) {
				continue;
			}
			if ((a[tx][ty] == '.' || a[tx][ty] == '@') && book[tx][ty] == 0) {// 可以往下走
				book[tx][ty] = 1;// 标记已走
				sum++;
//				 System.out.println(tx+" "+ty);
//				 for(int k=0;k<h;k++){
//					 for(int j=0;j<l;j++){
//						 System.out.print(book[k][j]);
//					 }
//					 System.out.println();
//				 }
				dfs(tx, ty);
			}
		}

	}

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

import java.util.Scanner;

public class Dfs1312 {

public static char a[][];

public static int book[][];

public static int l;

public static int h;

public static int sum;

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner in = new Scanner(System.in);

while (in.hasNext()) {

l = in.nextInt();

h = in.nextInt();

if (h == 0 && l == 0) {

break;

}

a = new char[h][l];

int startx = 0;

int starty = 0;

book = new int[h][l];// 没走的记录为0

for (int i = 0; i < h; i++) {

String str = in.next();

in.nextLine();

a[i] = str.toCharArray();

for (int j = 0; j < l; j++) {

if (a[i][j] == '@') {// 记录出发点

startx = i;

starty = j;

}

book[startx][starty] = 1;// 标记出发点已走

sum = 1;

dfs(startx, starty);

System.out.println(sum);

}

static void dfs(int x, int y) {

int[][] next = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

int tx, ty;

for (int i = 0; i < 4; i++) {// 计算下一点坐标

tx = x + next[i][0];

ty = y + next[i][1];

// 判断是否越界

if (tx < 0 || tx >= h || ty < 0 || ty >= l) {

continue;

}

if ((a[tx][ty] == '.' || a[tx][ty] == '@') && book[tx][ty] == 0) {// 可以往下走

book[tx][ty] = 1;// 标记已走

sum++;

// System.out.println(tx+" "+ty);

// for(int k=0;k<h;k++){

// for(int j=0;j<l;j++){

// System.out.print(book[k][j]);

// }

// System.out.println();

// }

dfs(tx, ty);

}

java实现桶排序

8月 29, 2017
0 条评论

了解桶排序

这个算法就好比有 11 个桶，编号从 0~10。每出现一个数，就在对应编号的桶中放一个小旗子，最后只要数数每个桶中有几个小旗子就 OK 了。例如 2 号桶中有 1 个小旗子，表示 2 出现了一次;3 号桶中有 1 个小旗子，表示 3 出现了一次;5 号桶中有 2 个小旗子，表示 5 出现了两次;8 号桶中有 1 个小旗子，表示 8 出现了一次。

如何实现桶排序

使用数组代替桶的作用,利用数组的下标直接排好顺序
每次遇到相应的旗子编号就对其对应的桶即相同的数组下标如a[5]的值+1用于记录出现几次
依次判断桶中的值即为输出的次数
依次按照次数输出桶的编号即数组的下标

利用java实现

题目:

考试成绩需要由小往大依次排序成绩范围为0-10 学生数为5人请依次输入学生成绩并进行排序

java code:

import java.util.Scanner;;
public class sortest {
	public static void main(String[] args) {
		
		int[] scores=new int[11];//定义一个空间大小为11的变量 0-10即11个
		Scanner input = new Scanner(System.in);//控制台等待输入
		for(int i=0;i<=10;i++){    //初始化scores值为0
			scores[i]=0;
		}
		for(int j=1;j<=5;j++){    //循环输入5名学生成绩
			System.out.println("请输入第"+j+"名学生成绩");
			int t=input.nextInt();
			scores[t]++;//计数
		}
		System.out.println("**************");
		for(int a=0;a<=10;a++){   //依次判断每个成绩
			for(int b=1;b<=scores[a];b++){   //依次判断每个成绩的人数
				System.out.println(a);
			}
		}
	}

	
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

import java.util.Scanner;;

public class sortest {

public static void main(String[] args) {

int[] scores=new int[11];//定义一个空间大小为11的变量 0-10即11个

Scanner input = new Scanner(System.in);//控制台等待输入

for(int i=0;i<=10;i++){ //初始化scores值为0

scores[i]=0;

}

for(int j=1;j<=5;j++){ //循环输入5名学生成绩

System.out.println("请输入第"+j+"名学生成绩");

int t=input.nextInt();

scores[t]++;//计数

}

System.out.println("**************");

for(int a=0;a<=10;a++){ //依次判断每个成绩

for(int b=1;b<=scores[a];b++){ //依次判断每个成绩的人数

System.out.println(a);

}

几种排序算法时间复杂度与稳定性比较

12月 13, 2015
0 条评论

排序算法	时间复杂度	稳定排序否
直接插入排序	O(n²)	稳定的
冒泡排序	O(n²)	稳定的
希尔排序	O(n²)	非稳定的
快速排序	O(nlogn)	非稳定的
堆排序	O(nlogn)	非稳定的
归并排序	O(nlogn)	稳定的

阅读剩余部分 –

【NOIP2014】生活大爆炸版石头剪刀布

12月 5, 2015
0 条评论

题目描述 Description

石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：

斯波克：《星际迷航》主角之一。蜥蜴人：《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。

现在，小A和小B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-„„”，而如果小B以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”

已知小A和小B一共进行N次猜拳。每一次赢的人得1分，输的得0分；平局两人都得0分。现请你统计N次猜拳结束之后两人的得分。

输入描述 Input Description

输入文件名为rps.in。

第一行包含三个整数：N，NA，NB，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。数与数之间以一个空格分隔。

第二行包含NA个整数，表示小A出拳的规律，第三行包含NB个整数，表示小B出拳的规律。其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”， 4表示“斯波克”。数与数之间以一个空格分隔。

输出描述 Output Description

输出文件名为rps.out。

输出一行，包含两个整数，以一个空格分隔，分别表示小A、小B的得分。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于100%的数据，0 < N ≤ 200，0 < NA ≤ 200， 0 < NB ≤ 200。

答案

#include<stdio.h>
#define MAXN 200
int r[5][5]={0,0,1,1,0,  
             1,0,0,1,0,  
             0,1,0,0,1,  
             0,0,1,0,1,  
             1,1,0,0,0,  
            }; 
int a[MAXN],b[MAXN];
int main()
{
	freopen("rps.in","r",stdin);
	freopen("rps.out","w",stdout);
	int n,na,nb;
	int suma=0,sumb=0;
	scanf("%d%d%d",&n,&na,&nb);
	for(int i=0;i<na;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<nb;i++)
        scanf("%d",&b[i]);
    for(int i=0;i<n;i++)
    {
        int c=a[i%na],d=b[i%nb];
		suma+=r[c][d];
		sumb+=r[d][c];
    }

    printf("%d %d",suma,sumb);   
    return 0;    
        
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

#include<stdio.h>

#define MAXN 200

int r[5][5]={0,0,1,1,0,

1,0,0,1,0,

0,1,0,0,1,

0,0,1,0,1,

1,1,0,0,0,

};

int a[MAXN],b[MAXN];

int main()

{

freopen("rps.in","r",stdin);

freopen("rps.out","w",stdout);

int n,na,nb;

int suma=0,sumb=0;

scanf("%d%d%d",&n,&na,&nb);

for(int i=0;i<na;i++)

scanf("%d",&a[i]);

for(int i=0;i<nb;i++)

scanf("%d",&b[i]);

for(int i=0;i<n;i++)

{

int c=a[i%na],d=b[i%nb];

suma+=r[c][d];

sumb+=r[d][c];

}

printf("%d %d",suma,sumb);

return 0;

}

阅读剩余部分 –

算法入门之开灯问题

12月 4, 2015
0 条评论

开灯问题属于C语言中一维数组中较为基础典型的一道练习

问题：

有n盏灯，编号为1~n。第一个人把所有灯都打开，第二个人按下所有编号为2的倍数的开关（这些灯将被关掉），第三个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），以此类推。一共有k个人，问最后有哪些灯开着？输入n和k,输出开着的灯的编号

样例输入：

7 3

样例输出：

1 5 6 7

【分析】

用a[1],a[2]…..a[n]来表示编号为1，2….n的灯
第二个人按下2的倍数，第三个人按下3的倍数可以通过第几盏灯除以第几个人取余数看是否为0
通过真假判断灯的亮灭

【代码】

#include<stdio.h>
#include<string.h>
#define maxn 1010
int a[maxn];
int main()
{
	int n,k,first=1;
	memset(a,0,sizeof(a));
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
	   for(int j=1;j<=n;j++)
	     if(j%i==0) a[j]=!a[j];
    for(int i=1;i<=n;i++)
       if(a[i])
       {
       	if(first)
       	  first=0;
 	else
 	  printf(" ");
 	  printf("%d",i);
       }
     printf("\n");
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

#include<stdio.h>

#include<string.h>

#define maxn 1010

int a[maxn];

int main()

{

int n,k,first=1;

memset(a,0,sizeof(a));

scanf("%d%d",&n,&k);

for(int i=1;i<=k;i++)

for(int j=1;j<=n;j++)

if(j%i==0) a[j]=!a[j];

for(int i=1;i<=n;i++)

if(a[i])

{

if(first)

first=0;

else

printf(" ");

printf("%d",i);

}

printf("\n");

return 0;

}

部分解释：

memset(a,0,sizeof(a)); 用来表示把数组a清零，他在#include<string.h> 中定义

接下来

for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
if(j%i==0) a[j]=!a[j];

依次用第几盏灯数除以当前第几个人取余数看是否为0，如果是则取反即1->0 ,0->1来表示灯的亮灭

接下来程序为了避免输出多余的空格，设置了一个标志变量first 开始时定义first=1即为真if(first) first=0;来管理当前输出变量是否为第一个，如果是则first为0即为假，后续每一个值前加一个空格

阅读剩余部分 –

计算线段长度

11月 6, 2015
0 条评论

总时间限制:: 1000ms
内存限制:: 65536kB

描述: 已知线段的两个端点的坐标A（Xa,Ya），B（Xb，Yb），求线段AB的长度。
输入: 共两行。
第一行是两个实数Xa，Ya，即A的坐标。
第二行是两个实数Xb，Yb，即B的坐标。
输入中所有实数的绝对值均不超过10000。
输出: 一个实数，即线段AB的长度，保留到小数点后3位。
样例输入
1 1 2 2 1 2 1 1 2 2
样例输出
1.414 1 1.414

答案：

#include<stdio.h>
#include<math.h>
int main()
{
float Xa,Ya,Xb,Yb;
scanf("%f%f%f%f",&Xa,&Ya,&Xb,&Yb);
float s=(Xa-Xb)* (Xa-Xb)+(Ya-Yb)*(Ya-Yb);
float t=sqrt(s);
printf("%.3f",t);
return 0;
}

1

2

3

4

5

6

7

8

9

10

11

#include<stdio.h>

#include<math.h>

int main()

{

float Xa,Ya,Xb,Yb;

scanf("%f%f%f%f",&Xa,&Ya,&Xb,&Yb);

float s=(Xa-Xb)* (Xa-Xb)+(Ya-Yb)*(Ya-Yb);

float t=sqrt(s);

printf("%.3f",t);

return 0;

}

标签算法下的文章

纪念一下刷的第100道水题

Red and Black

Problem Description

Input

Output

Sample Input

Sample Output

代码实现

java实现桶排序

了解桶排序

如何实现桶排序

利用java实现

题目:

java code:

几种排序算法时间复杂度与稳定性比较

【NOIP2014】生活大爆炸版石头剪刀布

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

答案

算法入门之开灯问题

计算线段长度

LOGO

近期文章

分类目录

近期评论

功能

博客统计

标签 算法 下的文章

纪念一下刷的第100道水题

Red and Black

Problem Description

Input

Output

Sample Input

Sample Output

代码实现

java实现桶排序

了解桶排序

如何实现桶排序

利用java实现

题目:

java code:

几种排序算法时间复杂度与稳定性比较

【NOIP2014】生活大爆炸版石头剪刀布

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

答案

算法入门之开灯问题

计算线段长度

LOGO

近期文章

标签

分类目录

近期评论

功能

博客统计

标签算法下的文章