深度优先

【算法】喷水装置（一）

发表于 2017-04-24 分类于算法竞赛
本文字数： 1.1k 阅读时长 ≈ 1 分钟

喷水装置（一）

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述

现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(1<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入

第一行m表示有m组测试数据
每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出

输出所用装置的个数

样例输入

2
5
2 3.2 4 4.5 6 
10
1 2 3 1 2 1.2 3 1.1 1 2

样例输出

1
2

题目表述的不准确，应该是R>1,不然这题就不好做了。

import java.util.Arrays;
import java.util.Scanner;

public class T2喷水装置1 {

	public static void main(String[] args) {
	
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int[] out=new int[n];
			
			for (int i = 0; i < out.length; i++) {
				int t=sc.nextInt();
				double[] data=new double[t];
				for (int j = 0; j < data.length; j++) {
					data[j]=sc.nextDouble();
				}
				out[i]=getNum(data);
			}
			for (int i = 0; i < out.length; i++) {
				System.out.println(out[i]);
			}
		}
	}

	private static int getNum(double[] data) {
		Arrays.sort(data);
		int ans=0;
		double m=20.0;
		for (int i = data.length-1; i >= 0; i--) {
			if(m>0){
				m=m-2*Math.pow(data[i]*data[i]-1, 0.5);
				ans++;
			}else break;
		}
		return ans;
	}
}

【DIY】拼图游戏-九宫格

发表于 2017-04-23 分类于 DIY程序
本文字数： 7.6k 阅读时长 ≈ 7 分钟

无聊用Jquery写的一个九宫格拼图游戏。。。。

代码部分：

<html xmlns="http://www.w3.org/1999/xhtml">
<meta charset="utf-8"/>
<head>
    <title>拼图游戏--九宫格</title>
    <script src="Scripts/jquery-1.4.1.min.js" type="text/javascript"></script>
    <script type="text/javascript">
        var kong = 9;
        var cunts = 0;
        var kaishi=false;
        var zhanting=false;
        $(function () {
            /*给所以方块注册点击事件*/
            $(".cl").click(function () {
                if(!kaishi){
                    alert('请先点击开始游戏吧~~~！');
                    return;
                }
                var t = this.id;/*获取单击块的id*/
                var index = Number(t.substring(3, t.length));/*获取块的编号*/
                var m ="#"+ t + " img";
                var s = $(m)[0].src;
                var arr=s.split('/');
                s='images/'+arr[arr.length-1];
                
                /*判断两个块，能不能交换，上下左右，编号时用到一个技巧*/
                //编号为 /*1  2  3 */
                         /*5  6  7 */
                         /*9 10  11 */
                /*上下 只需判断做差的绝对值是否为4，左右 只需判断做差的绝对值是否为1*/

                if (Math.abs(index - kong) == 1 || Math.abs(index - kong) == 4){
                    var a = "#Div" + kong;
                    var b = "#Div" + index;

                    var img1 = '<img src="'+s+'" id="img11" />';
                    var img2 = '<img src="images/9.jpg" id="img11" />';

                    /*动画效果*/
                    $(m).toggle(200,function(){
                        $(a).html(img1);
                        $(b).html(img2);
                    });
                    
                    $(a).removeClass("click");
                    $(this).addClass("click");/*添加点击样式*/
                    kong = index;
                    cunts++;
                    $("#myCunts").attr('value',cunts);
                }
                else {
                    $(this).hide(200,function(){
 
                    });
                    $(this).show(200,function() {
                      
                    });
                }
            });

            /*给所有方块注册鼠标进入事件，将背景变成黄色*/
            $(".cl").mousemove(function () {
                $(this).addClass("move");
            });

            /*给所有方块注册鼠标移出事件，去除鼠标进入时的样式*/
            $(".cl").mouseout(function () {
                $(this).removeClass("move");
            });

            /*开始游戏,打乱卡片，随机生成两个数，然后交换两个卡片*/
            $("#start").click(function(){
                if(kaishi){
                    alert('游戏已经开始了哦~~~！！');
                    return;
                }
                kaishi=true;

                for (var i = 0; i < 20; i++) {
                    
                    var r1=Math.round(Math.random()*(11));
                    var r2=Math.round(Math.random()*(11));

                    if(r1==0||r1==4||r1==8||r1==9||r2==0||r2==4||r2==8||r2==9) continue;

                    var a='#Div'+r1;
                    var b='#Div'+r2;

                    var m =a + " img";
                    var s = $(m)[0].src;
                    var arr=s.split('/');
                    s='images/'+arr[arr.length-1];

                    var mb =b + " img";
                    var sb = $(mb)[0].src;  
                    var arrb=sb.split('/');
                    sb='images/'+arrb[arrb.length-1];

                    var img1 = '<img src="'+s+ '" />';
                    var img2 = '<img src="'+sb+'" />';

                    $(a).html(img2);
                    $(b).html(img1);
                }
                myclock();
            });
            $("#stop").click(function(){
                if(kaishi==true&&zhanting==false)
                    alert('好吧，你说停就停吧！待会继续！');
                else
                    alert('还没开始暂停个毛线的啊~~~');
            });
            $("#oneGet").click(function(){
                if(confirm('这么容易就要放弃了吗？'))
                {
                    location.reload();
                }
            });

            /*游戏模式设置*/
            $("#g33").click(function(){
                alert('当前就是3*3模式呢！！');
            });
            $("#g44").click(function(){
                alert('ggg正在加班开发中，请稍等哦~~~！！');
            });
            $("#g55").click(function(){
                alert('ggg正在加班开发中，请稍等哦~~~！！');
            });
        });
        /*计时开始*/
        var times;
        function myclock(){
                var t=$("#time").val();
                t=t.substring(0,t.length-2);
                t=1+Number(t)+'ms';
                $("#time").attr('value',t);
                times=setTimeout("myclock()",100);
        }
    </script>
    <style type="text/css">
        body
        {
        	text-align:center;
            font-family: 'myface', serif;
            font-size: 24px;
            background-image: url('images/bg.jpg');
            color: #7605F7;
        }
        #node input{
            font-family: 'myface', serif;
            font-size: 14px;
            color: #272822;
        }
        #jishi input{
            font-family: 'myface', serif;
            font-size: 16px;
            color: #f0f;
            width: 150px;
        }
        @font-face {
           font-family: 'myface';
           src: url('ttf/myface.ttf'); 
        }
        #box
        {
        	width:550px;
        	height:550px;
        	background:#ccc;
        	margin:0 auto;
            padding: 10px;
            margin-left: 500px;
            border: 2px solid #fff;
        }
        .cl
        {
        	width:180px;
        	height:180px;
        	margin-left:3px;
        	margin-top:3px;
        	background:#fff;
        	float:left;
        	font-size:180px;
        }
        /*鼠标进入样式*/
        .move
        {
        	background:#f0f;
        }
        /*鼠标单击样式*/
        .click
        {
            background: #0026ff;
        }
        /*鼠标单击样式*/
        img
        {
        	width:170px;
        	height:170px;
            margin:5px;
        }
        #shezhi,#jishi,#nandu{
            width: 300px;
            height: 80px;
            float: left;
            margin: 20px; 
            text-align: left;
        }
        #node{
            width: 300px;
            height: 400px;
            float: left;
            margin-left: 100px; 
        }
        #jishi{
            font-size: 19px;
            text-align: left;
            line-height: 40px;
        }
    </style>
</head>
<body>
    <form id="form1" runat="server">
    <h3>九宫格--拼图游戏</h3>
    <div id="node">
        <div id="shezhi">
            <fieldset>
                <legend>操作设置</legend>
                <input type="button" name="" value="开始游戏" id="start">
                <input type="button" name="" value="暂停游戏" id="stop">
                <input type="button" name="" value="重新开始" id="oneGet">
            </fieldset>
        </div>
        <div id="nandu">
            <fieldset>
                <legend>难度设置</legend>
                <input type="button" name="" value="3*3模式" id="g33">
                <input type="button" name="" value="4*4模式" id="g44">
                <input type="button" name="" value="5*5模式" id="g55">
            </fieldset>
        </div>
        <div id="jishi">
            <fieldset>
                <legend>记录情况</legend>
                移动次数：<input type="text" name="" value="0" id="myCunts"><br>
                用时情况：<input type="text" name="" value="0000ms" id="time"><br>
                最好成绩：<input type="text" name="" value="20"><br>
            </fieldset>
        </div>
    </div>
    <div id="box">
        <div id="Div1" class="cl">
            <img src="images/1.jpg" id="img1" />
        </div>
        <div id="Div2" class="cl">
            <img src="images/2.jpg" id="img2" />
        </div>
        <div id="Div3" class="cl">
            <img src="images/3.jpg" id="img3" />
        </div>
        <div id="Div5" class="cl">
            <img src="images/5.jpg" id="img5" />
        </div>
        <div id="Div6" class="cl">
            <img src="images/6.jpg" id="img6" />
        </div>
        <div id="Div7" class="cl">
            <img src="images/7.jpg" id="img7" />
        </div>
        <div id="Div9" class="cl">
            <img src="images/9.jpg" id="img9" />
        </div>
        <div id="Div10" class="cl">
            <img src="images/10.jpg" id="img10" />
        </div>
        <div id="Div11" class="cl">
            <img src="images/11.jpg" id="img11" />
        </div>
    </div>
    </form>
</body>
</html>

【算法】骑士游历

发表于 2017-04-15 分类于算法竞赛
本文字数： 1.4k 阅读时长 ≈ 1 分钟

#1504 : 骑士游历
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在8x8的国际象棋棋盘上给定一只骑士（俗称“马”）棋子的位置(R, C)，小Hi想知道从(R, C)开始移动N步一共有多少种不同的走法。

输入
第一行包含三个整数，N，R和C。

对于40%的数据， 1 <= N <= 1000000

对于100%的数据， 1 <= N <= 1000000000 1 <= R, C <= 8

输出
从(R, C)开始走N步有多少种不同的走法。由于答案可能非常大，你只需要输出答案模1000000007的余数。

样例输入
2 1 1
样例输出

一个通俗的想法：f[k][i][j]，第k步可以到达(i,j)的步法总数。
f[k+1][i][j]是在第k步的基础上走1步到达(i,j)的步法总数。

import java.util.Scanner;

public class Main {

	static long[][][] data=new long[2][12][12];
	static int[] dx=new int[]{-2,-2,-1,-1,1,1,2,2};
	static int[] dy=new int[]{-1,1,-2,2,-2,2,-1,1};
	static int pre=0,cur=0;
	static int mod=1000000007;
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int r=sc.nextInt();
			int c=sc.nextInt();
			
			data[0][r][c]=1;
			pre=0;
			cur=1;
			
			for (int step = 1; step <= n; step++) {
				for (int i = 1; i <= 8; i++) {
					for (int j = 1; j <= 8; j++) {
						data[cur][i][j]=0;
					}
				}
				
				for (int i = 1; i <= 8; i++) {
					for (int j = 1; j <= 8; j++) {
						//八个方向
						for (int f = 0; f < 8; f++) {
							int x=i+dx[f];
							int y=j+dy[f];
							if(x>=1 && x<=8 && y>=1 && y<=8)
								data[cur][x][y]=(data[cur][x][y]+data[pre][i][j])%mod;
						}
					}
				}
				pre=pre^1;
				cur=cur^1;
			}
			long ans=0;
			for (int i = 1; i <= 8; i++) {
				for (int j = 1; j < 8; j++) {
					ans=(ans+data[pre][i][j])%mod;
				}
			}
			System.out.println(ans);
		}
	}
}